Počet záznamů: 1
A note on propositional proof complexity of some Ramsey-type statements
- 1.
SYSNO ASEP 0369652 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 A note on propositional proof complexity of some Ramsey-type statements Tvůrce(i) Krajíček, Jan (MU-W) SAI, ORCID Zdroj.dok. Archive for Mathematical Logic. - : Springer - ISSN 0933-5846
Roč. 50, 1-2 (2011), s. 245-255Poč.str. 11 s. Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova proof complexity ; Ramsey theorem ; resolution 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 CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000286668400014 EID SCOPUS 79251623828 DOI 10.1007/s00153-010-0212-9 Anotace A Ramsey statement denoted n -> (k)(2)(2) says that every undirected graph on n vertices contains either a clique or an independent set of size k. Any such valid statement can be encoded into a valid DNF formulaRAM(n, k) of size O(n(k)) and with terms of size ((k)(2)). Let r(k) be the minimal n for which the statement holds. We prove that RAM(r(k), k) requires exponential size constant depth Frege systems, answering a problem of Krishnamurthy and Moll [15]. As a consequence of Pudlak's work in bounded arithmetic [19] it is known that there are quasi-polynomial size constant depth Frege proofs of RAM(4(k), k), but the proof complexity of these formulas in resolution R or in its extension R(log) is unknown. We define two relativizations of the Ramsey statement that still have quasi-polynomial size constant depth Frege proofs but for which we establish exponential lower bound for R. 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