Počet záznamů: 1
Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- 1.
SYSNO ASEP 0369682 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 Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem Tvůrce(i) Thapen, Neil (MU-W) RID, SAI Zdroj.dok. Archive for Mathematical Logic. - : Springer - ISSN 0933-5846
Roč. 50, 7-8 (2011), s. 665-680Poč.str. 16 s. Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova bounded arithmetic ; proof complexity ; search problems Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd LC505 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000300094700001 EID SCOPUS 80054119010 DOI 10.1007/s00153-011-0240-0 Anotace 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. 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