Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
share
While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jeřábek's theory APC_1 (2007) and of higher levels of Buss's hierarchy S^i_2 (1986) has been a more elusive task. Even in the more restricted setting of Cook's theory PV (1975), known results often rely on a less natural formalization that encodes a complexity statement using a collection of sentences instead of a single sentence. This is done to reduce the quantifier complexity of the resulting sentences so that standard witnessing results can be invoked. In this work, we establish unprovability results for stronger theories and for sentences of higher quantifier complexity. In particular, we unconditionally show that APC_1 cannot prove strong complexity lower bounds separating the third level of the polynomial hierarchy. In more detail, we consider non-uniform average-case separations, and establish that APC_1 cannot prove a sentence stating that ∀ n ≥ n_0 ∃ f_n ∈Π_3-SIZE[n^d] that is (1/n)-far from every Σ_3-SIZE[2^n^δ] circuit. This is a consequence of a much more general result showing that, for every i ≥ 1, strong separations for Π_i-SIZE[poly(n)] versus Σ_i-SIZE[2^n^Ω(1)] cannot be proved in the theory T_PV^i consisting of all true ∀Σ^b_i-1-sentences in the language of Cook's theory PV. Our argument employs a convenient game-theoretic witnessing result that can be applied to sentences of arbitrary quantifier complexity. We combine it with extensions of a technique introduced by Krajíček (2011) that was recently employed by Pich and Santhanam (2021) to establish the unprovability of lower bounds in PV (i.e., the case i=1 above, but under a weaker formalization) and in a fragment of APC_1.
READ FULL TEXT