Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2507.13576 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908468068220928 |
|---|---|
| author | Monroe, Hunter |
| author_facet | Monroe, Hunter |
| contents | This paper proposes a characterization of when one axiomatic theory, as a proof system for tautologies, $p$-simulates another, by showing: (i)~if c.e. theory $\mathcal{S}$ efficiently interprets $\mathcal{S}{+}ϕ$, then $\mathcal{S}$ $p$-simulates $\mathcal{S}{+}ϕ$ (Jeřábek in Pudlák17 proved simulation), since the interpretation maps an $\mathcal{S}{+}ϕ$-proof whose lines are all theorems into an $\mathcal{S}$-proof; (ii)~$\mathcal{S}$ proves ``$\mathcal{S}$ efficiently interprets $\mathcal{S}{+}ϕ$'' iff $\mathcal{S}$ proves ``$\mathcal{S}$ $p$-simulates $\mathcal{S}{+}ϕ$'' (if so, $\mathcal{S}$ already proves the $Π_1$ theorems of $\mathcal{S}{+}ϕ$). To explore whether this framework conceivably resolves other open questions, the paper formulates conjectures stronger than ``no optimal proof system exists'' that imply Feige's Hypothesis, the existence of one-way functions, and circuit lower bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13576 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Proposed Characterization of p-Simulation Between Theories Monroe, Hunter Computational Complexity Logic This paper proposes a characterization of when one axiomatic theory, as a proof system for tautologies, $p$-simulates another, by showing: (i)~if c.e. theory $\mathcal{S}$ efficiently interprets $\mathcal{S}{+}ϕ$, then $\mathcal{S}$ $p$-simulates $\mathcal{S}{+}ϕ$ (Jeřábek in Pudlák17 proved simulation), since the interpretation maps an $\mathcal{S}{+}ϕ$-proof whose lines are all theorems into an $\mathcal{S}$-proof; (ii)~$\mathcal{S}$ proves ``$\mathcal{S}$ efficiently interprets $\mathcal{S}{+}ϕ$'' iff $\mathcal{S}$ proves ``$\mathcal{S}$ $p$-simulates $\mathcal{S}{+}ϕ$'' (if so, $\mathcal{S}$ already proves the $Π_1$ theorems of $\mathcal{S}{+}ϕ$). To explore whether this framework conceivably resolves other open questions, the paper formulates conjectures stronger than ``no optimal proof system exists'' that imply Feige's Hypothesis, the existence of one-way functions, and circuit lower bounds. |
| title | A Proposed Characterization of p-Simulation Between Theories |
| topic | Computational Complexity Logic |
| url | https://arxiv.org/abs/2507.13576 |