"We define a new NP search problem, the %22local improvement%22 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 %22type-2%22 NP search problems, which take second-order objects as parameters: (c) 2011 Elsevier B.V. All rights reserved."@en . . "The provably total NP search problems of weak second order bounded arithmetic"@en . "28"^^ . "0168-0072" . "NL - Nizozemsko" . . "Thapen, Neil" . . "The provably total NP search problems of weak second order bounded arithmetic" . "RIV/67985840:_____/11:00359552" . "P(IAA100190902), P(LC505), Z(AV0Z10190503)" . . . . "RIV/67985840:_____/11:00359552!RIV12-AV0-67985840" . . "224925" . "The provably total NP search problems of weak second order bounded arithmetic" . . "6" . . "Kolodziejczyk, L.. A." . . "Annals of Pure and Applied Logic" . "2"^^ . "3"^^ . "We define a new NP search problem, the %22local improvement%22 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 %22type-2%22 NP search problems, which take second-order objects as parameters: (c) 2011 Elsevier B.V. All rights reserved." . . . "Nguyen, Phuong" . "The provably total NP search problems of weak second order bounded arithmetic"@en . "[9E27C181F804]" . . "162" . . . . . "10.1016/j.apal.2010.12.002" . "complexity; fragments"@en . "000289022500002" . . .