3 papers
cs.CC2026
Hardness Conjectures as Information Constraints: Does Complexity Theory Need New Axioms?
Hunter Monroe
We prove that no length-optimal propositional proof system exists if and only if every sound theory with polynomial-time decidable axioms fails to simu…
cs.CC2026
Toward a Characterization of Simulation Between Arithmetic Theories
Hunter Monroe
We study when a sound arithmetic theory with polynomial-time decidable axioms has polynomial-size proofs of for a true senten…
cs.CC2025
A Proposed Characterization of p-Simulation Between Theories
Hunter Monroe
This paper proposes a characterization of when one axiomatic theory, as a proof system for tautologies, -simulates another, by showing: (i)~if c.e. theory efficien…