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 33-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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.