Bounded arithmetic and the polynomial hierarchy (Q1177041): Difference between revisions

The authors assume familarity with the book of \textit{S. Buss} [Bounded arithmetic (1986; Zbl 0649.03042)]. They show that (1) \(T_ 2^ i=S_ 2^{i+1}\) implies \(\Sigma^ p_{i+1}\subseteq\Delta^ p_{i+1}/\text{poly}\). (For this result they use a Herbrand-type witnessing theorem for \(\exists\forall\exists\Pi^ b_ i\)-formulas provable in \(T^ i_ 2\), where the witnessing functions are in \(\square^ p_{i+1}\)). (2) \(S_ 2(\alpha)\) and \(I\Delta_ 0(f)\) are not finitely axiomatizable.