research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleExponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas
Bibtex cite IDRACTI-RU1-2012-19
Booktitle SAT
Series Theory and Applications of Satisfiability Testing – SAT 2012
Year published 2012
Pages 327-340
Organization 15th International Conference, Trento, Italy, June 17-20, 2012.
DOI 10.1007/978-3-642-31612-8_25
We consider the performance of a number of DPLL algorithms on random 3-CNF formulas with n variables and m = rn clauses. A long series of papers analyzing so-called “myopic” DPLL algorithms has provided a sequence of lower bounds for their satisfiability threshold. Indeed, for each myopic algorithm A it is known that there exists an algorithm-specific clause-density, rA , such that if r 2.78 and the same is true for generalized unit clause for all r > 3.1. Our results imply exponential lower bounds for many other myopic algorithms for densities similarly close to the corresponding rA .
Achlioptas, Dimitris
Menchaca-Mendez, Ricardo
DPLL.pdf (main file)
Publication ID967