English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

While there has been progress in establishing the unprovability of complexitystatements in lower fragments of bounded arithmetic, understanding the limitsof Je\v{r}\'abek's theory $APC_1$ (2007) and of higher levels of Buss'shierarchy $S^i_2$ (1986) has been a more elusive task. Even in the morerestricted setting of Cook's theory PV (1975), known results often rely on aless natural formalization that encodes a complexity statement using acollection of sentences instead of a single sentence. This is done to reducethe quantifier complexity of the resulting sentences so that standardwitnessing results can be invoked.  In this work, we establish unprovability results for stronger theories andfor sentences of higher quantifier complexity. In particular, weunconditionally show that $APC_1$ cannot prove strong complexity lower boundsseparating the third level of the polynomial hierarchy. In more detail, weconsider non-uniform average-case separations, and establish that $APC_1$cannot prove a sentence stating that $\forall n \ge n_0\;\exists\,f_n \in\Pi_{3}$-$SIZE[n^d]$ that is $(1/n)$-far from every$\Sigma_{3}$-$SIZE[2^{n^{\delta}}]$ circuit. This is a consequence of a muchmore general result showing that, for every $i \geq 1$, strong separations for$\Pi_{i}$-$SIZE[poly(n)]$ versus $\Sigma_{i}$-$SIZE[2^{n^{\Omega(1)}}]$ cannotbe proved in the theory $T_{PV}^i$ consisting of all true $\forall\Sigma^b_{i-1}$-sentences in the language of Cook's theory PV.  Our argument employs a convenient game-theoretic witnessing result that canbe applied to sentences of arbitrary quantifier complexity. We combine it withextensions of a technique introduced by Kraj\'i\v{c}ek (2011) that was recentlyemployed by Pich and Santhanam (2021) to establish the unprovability of lowerbounds in PV (i.e., the case $i=1$ above, but under a weaker formalization) andin a fragment of $APC_1$.

Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic