Fragments of bounded arithmetic and bounded query classes

Open Access
Publisher Website
Google Scholar
Abstract
We characterize functions and predicates Σ i + 1 b \Sigma _{i + 1}^b -definable in S 2 i S_2^i . In particular, predicates Σ i + 1 b \Sigma _{i + 1}^b -definable in S 2 i S_2^i are precisely those in bounded query class P Σ i p [ O ( log ⁡ n ) ] {P^{\Sigma _i^p}}[O(\log n)] (which equals to Log Space Σ i p \operatorname {Log}\;{\text {Space}}^{\Sigma _i^p} by [B-H, W]). This implies that S 2 i ≠ T 2 i S_2^i \ne T_2^i unless P Σ i p [ O ( log ⁡ n ) ] = Δ i + 1 p {P^{\Sigma _i^p}}[O(\log n)] = \Delta _{i + 1}^p . Further we construct oracle A A such that for all i ≥ 1 i \geq 1 ...

This publication has 13 references indexed in Scilit: