Total space in resolution

0466751 - MÚ 2017 RIV US eng J - Journal Article
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
R&D Projects: GA ČR GBP202/12/G061
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : total space * resolution random CNFs * proof complexity
Subject RIV: BA - General Mathematics
Impact factor: 1.433, year: 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.
Permanent Link: http://hdl.handle.net/11104/0264987