Počet záznamů: 1

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

  1. 1.
    0359552 - MU-W 2012 RIV NL eng J - Článek v odborném periodiku
    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
    Grant CEP: GA AV ČR IAA100190902; GA MŠk LC505
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: complexity * fragments
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.450, rok: 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.
    Trvalý link: http://hdl.handle.net/11104/0197323
    Název souboruStaženoVelikostKomentářVerzePřístup
    Thapen.pdf1500.9 KBVydavatelský postprintvyžádat