Hardness Conjectures as Information Constraints: Does Complexity Theory Need New Axioms?

Abstract

We prove that no length-optimal propositional proof system exists if and only if every sound theory $\mathcal{S}\supseteq S_2^1$ with polynomial-time decidable axioms fails to simulate $S_2^1+\mathsf{Exp}+{\varphi }_{BB}(k)$ for all sufficiently large $k$, where ${\varphi }_{BB}(k)$ asserts the exact $k$-state Busy Beaver value and $\mathsf{Exp}$ asserts total binary exponentiation. Thus a widely believed proof-complexity conjecture admits an information-constraint formulation in terms of Busy Beaver values. For finitely axiomatized sequential $\mathcal{S}$, a Kolmogorov Blindness conjecture predicts exponential proof-length lower bounds for true randomness extensions, even after adjoining another true randomness axiom if the target remains random conditional on the added string. We also show that a separate hierarchy-level information constraint implies noncollapse of the polynomial hierarchy. These information constraints parallel known results: Liu--Pass characterize one-way functions by average-case hardness of time-bounded Kolmogorov complexity $K^t$; Allender et al. relate $KT$ complexity to circuit size up to polynomial factors; Ball et al. characterize key agreement and one-way functions using one interactive problem with different gap parameters. We propose a research program to unify these connections through precise constraints on proof size, average-case time, and circuit size, and ask whether a common framework could justify a new axiom schema for complexity theory. Independence from $ZFC$ remains open. Unconditionally, for each fixed sound $\mathcal{S}$, any fixed sound computably axiomatized certifying theory extending $EA$ certifies simulation of only finitely many randomness extensions of $\mathcal{S}$. Defining efficiency as provable efficiency in a fixed theory relocates this difficulty.

arXiv commentv3: Refutes our Higher Relative Consistency conjecture, extends the positive simulation result, replaces certificate-based randomness hypotheses with Kolmogorov Blindness and its conditional density and pairwise consequences. v2: Unifies KH and SETH-K-Finite with the companion paper, adds the Theorist vs Nature game, tools from economic theory, adds figures, and restates circuit hardness for MKTP