Počet záznamů: 1
The provably total search problems of bounded arithmetic
- 1.
SYSNO ASEP 0369680 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název The provably total search problems of bounded arithmetic Tvůrce(i) Skelley, A. (CA)
Thapen, Neil (MU-W) RID, SAIZdroj.dok. Proceedings of the London Mathematical Society - ISSN 0024-6115
Roč. 103, č. 1 (2011), s. 106-138Poč.str. 33 s. Jazyk dok. eng - angličtina Země vyd. GB - Velká Británie Klíč. slova Pigeonhole principle ; polynomial hierarchy ; local search Vědní obor RIV BA - Obecná matematika CEP LC505 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000292311700004 EID SCOPUS 79960135887 DOI 10.1112/plms/pdq044 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2012
Počet záznamů: 1