Počet záznamů: 1

Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem

  1. 1.
    0369682 - MU-W 2012 RIV DE eng J - Článek v odborném periodiku
    Thapen, Neil
    Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem.
    Archive for Mathematical Logic. Roč. 50, 7-8 (2011), s. 665-680 ISSN 1432-0665
    Grant CEP: GA AV ČR IAA100190902; GA MŠk LC505; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: bounded arithmetic * proof complexity * search problems
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.341, rok: 2011
    http://www.springerlink.com/content/l19kr20362065t86/

    We give a new characterization of the strict "Sbjjb sentences provable using Sbkbk induction, for 1 ≤ j ≤ k. As a small application we show that, in a certain sense, Buss’s witnessing theorem for strict Sbkbk formulas already holds over the relatively weak theory PV. We exhibit a combinatorial principle with the property that a lower bound for it in constant-depth Frege would imply that the narrow CNFs with short depth j Frege refutations form a strict hierarchy with j, and hence that the relativized bounded arithmetic hierarchy can be separated by a family of "Sb1b1 sentences.
    Trvalý link: http://hdl.handle.net/11104/0203691
    Název souboruStaženoVelikostKomentářVerzePřístup
    Thapen1.pdf1239.5 KBVydavatelský postprintvyžádat