Počet záznamů: 1
Total space in resolution
- 1.
SYSNO ASEP 0466751 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 Total space in resolution Tvůrce(i) Bonacina, I. (SE)
Galesi, N. (IT)
Thapen, Neil (MU-W) RID, SAIZdroj.dok. Siam Journal on Computing - ISSN 0097-5397
Roč. 45, č. 5 (2016), s. 1894-1909Poč.str. 16 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova total space ; resolution random CNFs ; proof complexity Vědní obor RIV BA - Obecná matematika CEP GBP202/12/G061 GA ČR - Grantová agentura ČR Institucionální podpora MU-W - RVO:67985840 UT WOS 000387321500007 EID SCOPUS 85010644516 DOI 10.1137/15M1023269 Anotace We show quadratic lower bounds on the total space used in resolution refutations of random $k$-CNFs over $n$ variables and of the graph pigeonhole principle and the bit pigeonhole principle for $n$ holes. This answers the open problem of whether there are families of $k$-CNF formulas of polynomial size that require quadratic total space in resolution. The results follow from a more general theorem showing that, for formulas satisfying certain conditions, in every resolution refutation there is a memory configuration containing many clauses of large width. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2017
Počet záznamů: 1