Fragments of bounded arithmetic and bounded query classes

Abstract:

We characterize functions and predicates $\Sigma _{i + 1}^b$-definable in $S_2^i$. In particular, predicates $\Sigma _{i + 1}^b$-definable in $S_2^i$ are precisely those in bounded query class ${P^{\Sigma _i^p}}[O(\log n)]$ (which equals to $\operatorname {Log}\;{\text {Space}}^{\Sigma _i^p}$ by [B-H, W]). This implies that $S_2^i \ne T_2^i$ unless ${P^{\Sigma _i^p}}[O(\log n)] = \Delta _{i + 1}^p$. Further we construct oracle $A$ such that for all $i \geq 1$: ${P^{\Sigma _i^p(A)}}[O(\log n)] \ne \Delta _{i + 1}^p(A)$. It follows that $S_2^i(\alpha ) \ne T_2^i(\alpha )$ for all $i \geq 1$. Techniques used come from proof theory and boolean complexity.