Hard satisfiable instances for DPLL-type algorithms

DOI10.1007/s10958-005-0105-3zbMath1101.68600OpenAlexW2024260528WikidataQ57101178 ScholiaQ57101178MaRDI QIDQ2577593

Sergey I. Nikolenko

Publication date: 3 January 2006

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-005-0105-3

zbMATH Keywords

propositional satisfiability problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Limitations of restricted branching in clause learning

Cites Work

• Unnamed Item
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• On the complexity of regular resolution and the Davis-Putnam procedure
• New worst-case upper bounds for SAT
• SAT local search algorithms: Worst-case study
• Algorithms for Sat and upper bounds on their complexity
• Hard examples for resolution
• A sharp threshold in proof complexity
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving