Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with heuristic computation:
TR12-141 | 22nd October 2012
Dmitry Itsykson, Dmitry Sokolov

Lower bounds for myopic DPLL algorithms with a cut heuristic

The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are ... more >>>

ISSN 1433-8092 | Imprint