Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with DPLL algorithms:
TR04-041 | 18th May 2004
Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to tree-like resolution proofs. Therefore, lower bounds for tree-like resolution (which ... more >>>

TR10-198 | 13th December 2010
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov

Parameterized Bounded-Depth Frege is Not Optimal

A general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that framework the parameterized version of any proof system is not fpt-bounded for some technical reasons, but we remark that this question becomes much more interesting if we restrict ourselves to those parameterized contradictions ... more >>>

ISSN 1433-8092 | Imprint