The provably total NP search problems of weak second order bounded arithmetic (Q639650)

In the paper a new NP search problem, the ``local improvement'' principle about labelling of an acyclic, bounded-degree graph, is defined. It is shown that, provably in PV, it chracterizes the \(\forall \Sigma^{b}_{1}\) consequences of \(V_{2}^{1}\) and that natural restrictions of it characterize the \(\forall \Sigma^{b}_{1}\) consequences of \(U^{1}_{2}\) and of the bounded arithmetic hierarchy. It is also shown that over \(V^{0}\) it characterizes the \(\forall \Sigma^{B}_{0}\) consequences of \(V^{1}\) and that in some sense a minaturized version of the principle gives a new characterization of the \(\forall \Pi ^{b}_{1}\) consequences of \(S^{1}_{2}\). Throughout the paper the search problems are ``type-2'' NP search problems which take second-order objects as parameters.