Polynomial consistency-speedup conjecture for bounded-arithmetic theories
Polynomial consistency-speedup conjecture for bounded-arithmetic theories
Let be a sound theory whose axioms are definable by a formula, and let . A sound theory whose axioms are definable by a formula should exist such that
Polynomial consistency-speedup conjecture. For every sound theory and every , there exists a sound theory such that
This conjecture proposes that arbitrarily large polynomial lower bounds for the -length of consistency statements can still be obtained while both theories have bounded-arithmetic definable axiom sets. The preceding discussion explains why the analogous unrestricted lower-bound theorem does not immediately extend to polynomial-time theories, leaving this bounded-arithmetic formulation as a speculative possibility.
Sources & referencesView supporting material
Primary source
Joost J. Joosten, “Propositional proof systems and fast consistency provers”, arXiv:2004.05431 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.