Hunter Monroe

Hunter Monroe

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.

Hunter Monroe

We study when a sound arithmetic theory $\mathcal S{\supseteq}S^1_2$ with polynomial-time decidable axioms efficiently proves the bounded consistency statements $Con_{\mathcal S{+}ϕ}(n)$ for a true sentence $ϕ$. Equivalently, we ask when $\mathcal S$, viewed as a proof system, simulates $\mathcal S{+}ϕ$. The paper's two unconditional contributions constrain possible characterizations. First, for finitely axiomatized sequential $\mathcal S$, if $EA{\vdash}Con_{\mathcal S}{\rightarrow}Con_{\mathcal S{+}ϕ}$, then $\mathcal S$ interprets $\mathcal S{+}ϕ$, implying ${\mathcal S}{\vdash^{n^{O(1)}}}Con_{\mathcal S}(p(n)){\rightarrow}Con_{\mathcal S{+}ϕ}(n)$ for some polynomial $p$, and hence ${\mathcal S}{\vdash^{n^{O(1)}}}Con_{\mathcal S{+}ϕ}(n)$. Second, if $\mathcal S$ fails to simulate $\mathcal S{+}ϕ$ for some true $ϕ$, then for all sufficiently large $k$ it also fails for $ϕ_{BB}(k)$ asserting the exact value of the $k$-state Busy Beaver function. Informally, any argument showing that $\mathcal S$ fails to simulate some $\mathcal S{+}ϕ$ also yields unprovable $ϕ_{BB}(k)$ witnessing the same obstruction. These results suggest that relative consistency strength is a serious candidate for governing when simulation is possible, while leaving open whether it is the correct criterion. The paper's central conjectural proposal is that the above sufficient condition is also necessary: if $EA{\not\vdash}Con_{\mathcal S}{\rightarrow}Con_{\mathcal S{+}ϕ}$, then for every constant $c{>}0$, ${\mathcal S}{\not\vdash^{n^c}}Con_{\mathcal S{+}ϕ}(n)$. Under this proposal, hardness follows in canonical cases where $ϕ$ is $Con_{\mathcal S}$ or a Kolmogorov-randomness axiom. The latter yields further conjectural consequences and extensions.