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

0359552 - MÚ 2012 RIV NL eng J - Journal Article
Kolodziejczyk, L. A. - Thapen, Neil - Nguyen, Phuong
The provably total NP search problems of weak second order bounded arithmetic.
Annals of Pure and Applied Logic. Roč. 162, č. 6 (2011), s. 419-446. ISSN 0168-0072. E-ISSN 1873-2461
R&D Projects: GA AV ČR IAA100190902; GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : complexity * fragments
Subject RIV: BA - General Mathematics
Impact factor: 0.450, year: 2011
http://www.sciencedirect.com/science/article/pii/S0168007210001491

We define a new NP search problem, the "local improvement" principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in PV, it characterizes the for all Sigma(b)(1) consequences of V-2(1) and that natural restrictions of it characterize the for all Sigma(b)(1) consequences of U-2(1) and of the bounded arithmetic hierarchy. We also show that over V-0 it characterizes the for all Sigma(B)(0) consequences of V-1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the for all Pi(b)(1) consequences of S-2(1). Throughout our search problems are "type-2" NP search problems, which take second-order objects as parameters: (c) 2011 Elsevier B.V. All rights reserved.
Permanent Link: http://hdl.handle.net/11104/0197323