Busy Beaver and Kolmogorov-random-string conjectures imply Feige's Hypothesis
Busy Beaver and Kolmogorov-random-string conjectures imply Feige's Hypothesis
Let Feige's Hypothesis be the assertion that no efficient algorithm can prove the unsatisfiability of a random -SAT formula with high probability, even when the formula has a small number of clauses. Let the Busy Beaver proof-size conjecture and the Kolmogorov-random-string proof-size conjecture be the two conjectures stated above. Feige implication conjecture. Either the Busy Beaver proof-size conjecture or the Kolmogorov-random-string proof-size conjecture implies Feige's Hypothesis.
Sources & referencesView supporting material
Primary source
Hunter Monroe, “A Proposed Characterization of p-Simulation Between Theories”, arXiv:2507.13576 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.