Hardness as an Information Constraint: A Unifying Meta-Complexity Assumption
2026-06-02 • Computational Complexity
Computational Complexity
AI summaryⓘ
Monroe (2026) explores the idea that if no perfect proof system exists, this reflects a fundamental limit on what arithmetical theories can prove about very hard problems, like Busy Beaver values or certain random strings called Kolmogorov-random strings. They show that this limit, called Kolmogorov Hardness (KH), relates to key open questions in computational complexity, such as why some computational problems seem inherently difficult and why certain complexity classes stay distinct. Monroe proposes that these limitations act like reflection principles that might be independent of standard mathematical frameworks, suggesting new directions for research about the foundations of complexity theory.
Optimal proof systemBusy Beaver functionKolmogorov randomnessComputational complexityProof theoryReflection principlesPolynomial hierarchy (PH)One-way functionsDerandomizationNatural proofs
Authors
Hunter Monroe
Abstract
Monroe (2026) shows that the nonexistence of an optimal proof system can be read as an information constraint regarding canonical hard instances: no sound arithmetic theory simulates the extensions adjoining sufficiently large, unprovable Busy Beaver values. Furthermore, if the best-known route to simulation is also necessary -- that is, if simulation requires a relative-consistency explanation over a weak base theory -- then the same constraint holds for inaccessible Kolmogorov-randomness facts. Call this Kolmogorov Hardness (KH). We argue that open questions in computational complexity can likewise be reformulated as information constraints involving Kolmogorov-random strings. Variants of KH yield, as conditional consequences, dense families of small hard tautologies, no-mutual-help phenomena for independent random axioms, PH noncollapse with explicit dense separators at each level, $SAT\notin P/poly$, and canonical disjoint NP pairs arising from random-axiom constructions. Time-bounded and sparse-support variants extend the same template to one-way functions via Liu--Pass, derandomization, natural-proofs-style limitations, and Feige-style random refutation. This framework gives a unified working model of complexity theorists' beliefs, organized around canonical hard instances. It seems self-evident that efficient proofs in a theory should not leverage true randomness facts the theory cannot verify. Yet the structural features of KH and its variants suggest they may be formally independent of standard metatheories. They behave like reflection principles; their internal readings fail in nonstandard models even when the corresponding external readings are true; and the same information constraints may apply to the metatheories themselves. We propose a research program: extend the model, resolve questions of formal independence, and identify which principles are potential new axioms.