Počet záznamů: 1
Total space in resolution
- 1.0466751 - MÚ 2017 RIV US eng J - Článek v odborném periodiku
Bonacina, I. - Galesi, N. - Thapen, Neil
Total space in resolution.
Siam Journal on Computing. Roč. 45, č. 5 (2016), s. 1894-1909. ISSN 0097-5397. E-ISSN 1095-7111
Grant CEP: GA ČR GBP202/12/G061
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: total space * resolution random CNFs * proof complexity
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.433, rok: 2016
http://epubs.siam.org/doi/10.1137/15M1023269
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.
Trvalý link: http://hdl.handle.net/11104/0264987
Název souboru Staženo Velikost Komentář Verze Přístup Thapen2.pdf 8 493.9 KB Vydavatelský postprint vyžádat
Počet záznamů: 1