Lower bounds for myopic DPLL algorithms with a cut heuristic

DOI10.1007/978-3-642-25591-5_48zbMATH Open1350.68120OpenAlexW95899737MaRDI QIDQ3104641FDOQ3104641

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

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

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)

Cited In (4)

• 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
• Automata, Languages and Programming

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)