Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-062 | 29th April 2026 21:52

Toward a Characterization of Simulation Between Arithmetic Theories

RSS-Feed




TR26-062
Authors: Hunter Monroe
Publication: 30th April 2026 17:41
Downloads: 38
Keywords: 


Abstract:

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{+}\phi}(n)$ for a true sentence $\phi$. Equivalently, we ask when $\mathcal S$, viewed as a proof system, simulates $\mathcal S{+}\phi$. 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{+}\phi}$, then $\mathcal S$ interprets $\mathcal S{+}\phi$, implying $\mathcal S{\vdash^{n^{O(1)}}}Con_{\mathcal S}(p(n)){\rightarrow}Con_{\mathcal S{+}\phi}(n)$ for some polynomial $p$, and hence $\mathcal S{\vdash^{n^{O(1)}}}Con_{\mathcal S{+}\phi}(n)$. Second, if $\mathcal S$ fails to simulate $\mathcal S{+}\phi$ for some true $\phi$, then for all sufficiently large $k$ it also fails for $\phi_{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{+}\phi$ also yields unprovable $\phi_{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{+}\phi}$, then for every constant $c{>}0$, $\mathcal S\not{\vdash^{n^c}}Con_{\mathcal S{+}\phi}(n)$. Under this proposal, hardness follows in canonical cases where $\phi$ is $Con_{\mathcal S}$ or a Kolmogorov-randomness axiom. The latter yields further conjectural consequences and extensions.



ISSN 1433-8092 | Imprint