Počet záznamů: 1

The provably total search problems of bounded arithmetic

  1. 1.
    0369680 - MU-W 2012 RIV GB eng J - Článek v odborném periodiku
    Skelley, A. - Thapen, Neil
    The provably total search problems of bounded arithmetic.
    Proceedings of the London Mathematical Society. Roč. 103, č. 1 (2011), s. 106-138 ISSN 0024-6115
    Grant CEP: GA MŠk LC505
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: Pigeonhole principle * polynomial hierarchy * local search
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 1.324, rok: 2011
    http://plms.oxfordjournals.org/content/103/1/106

    We give combinatorial principles GI(k), based on k-turn games, which are complete for the class of NP search problems provably total at the kth level T(2)(k) of the bounded arithmetic hierarchy and hence characterize the for all Sigma(b)(1) consequences of T(2)(k). Our argument uses a translation of first-order proofs into large, uniform propositional proofs in a system in which the soundness of the rules can be witnessed by polynomial time reductions between games. We show that for all(Sigma) over cap (b)(1)(alpha) conservativity of T(2)(i+1) (alpha) over T(2)(i)(alpha) already implies. for all(Sigma) over cap (b)(1)(a) conservativity of T(2)(alpha) over T(2)(i)(alpha). We translate this into propositional form and give a polylogarithmic width CNF (GI(3)) over bar such that if (GI(3)) over bar has small R(log) refutations then so does any polylogarithmic width CNF which has small constant depth refutations. We prove a resolution lower bound for (GI(3)) over bar.
    Trvalý link: http://hdl.handle.net/11104/0203689
    Název souboruStaženoVelikostKomentářVerzePřístup
    Thapen2.pdf6329.4 KBVydavatelský postprintvyžádat