Lower bounds for myopic DPLL algorithms with a cut heuristic

DOI10.1007/978-3-642-25591-5_48MaRDI QIDQ3104641zbMATH OpenOpenAlexFDO

Authors Dmitry Itsykson, Dmitry Sokolov

Publication date 16 December 2011

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-25591-5_48

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Automata, Languages and Programming
• Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
• Hard satisfiable instances for DPLL-type algorithms
• Exponential bounds for DPLL below the satisfiability threshold

Cited in

(4)

• Automata, Languages and Programming
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• Hard satisfiable instances for DPLL-type algorithms

This page was built for publication: Lower bounds for myopic DPLL algorithms with a cut heuristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3104641)