0380502 - MÚ 2013 RIV NL eng J - Journal Article
Krajíček, Jan
A note on SAT algorithms and proof complexity.
Information Processing Letters. Roč. 112, č. 12 (2012), s. 490-493. ISSN 0020-0190. E-ISSN 1872-6119
R&D Projects: GA AV ČR IAA100190902
Institutional research plan: CEZ:AV0Z10190503
Keywords : computational complexity
Subject RIV: BA - General Mathematics
Impact factor: 0.488, year: 2012
http://www.sciencedirect.com/science/article/pii/S0020019012000774

We apply classical proof complexity ideas to transfer lengths-of-proofs lower bounds for a propositional proof system P into examples of hard unsatisfiable formulas for a class Alg(P) of SAT algorithms determined by P. The class Alg(P) contains those algorithms M for which P proves in polynomial size tautologies expressing the soundness of M. For example, the class Alg(F-d) determined by a depth d Frege system contains the commonly considered enhancements of DPLL (even for small d). Exponential lower bounds are known for all F-d. Such results can be interpreted as a form of consistency of P not equal NP. Further we show how the soundness statements can be used to find hard satisfiable instances, if they exist.
Permanent Link: http://hdl.handle.net/11104/0211194