Polynomial consistency-speedup conjecture for bounded-arithmetic theories

Let SS be a sound theory whose axioms are definable by a Δ1b(S21)\Delta^b_1(S^1_2) formula, and let lωl\in\omega. A sound theory TT whose axioms are definable by a Δ1b(S21)\Delta^b_1(S^1_2) formula should exist such that

ConT(x)S>xl.\left\|\operatorname{Con}_T(\underline{x})\right\|_S>x^l.

Polynomial consistency-speedup conjecture. For every sound Δ1b(S21)\Delta^b_1(S^1_2) theory SS and every lωl\in\omega, there exists a sound Δ1b(S21)\Delta^b_1(S^1_2) theory TT such that

ConT(x)S>xl.\left\|\operatorname{Con}_T(\underline{x})\right\|_S>x^l.

This conjecture proposes that arbitrarily large polynomial lower bounds for the SS-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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.