The provably total NP search problems of weak second order bounded arithmetic (Q639650): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.apal.2010.12.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2053365988 / rank | |||
Normal rank |
Revision as of 00:55, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The provably total NP search problems of weak second order bounded arithmetic |
scientific article |
Statements
The provably total NP search problems of weak second order bounded arithmetic (English)
0 references
22 September 2011
0 references
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.
0 references
bounded arithmetic
0 references
search problems
0 references
two-sorted
0 references
second-order arithmetic
0 references