Hard random 3-SAT problems and the Davis-Putnam procedure

DOI10.1016/0004-3702(95)00051-8OpenAlexW2015932695WikidataQ126593077 ScholiaQ126593077MaRDI QIDQ2674184

Jon W. Freeman

Publication date: 22 September 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(95)00051-8

zbMATH Keywords

satisfiabilityDavis-Putnam procedurerandom 3-SATcomplexity decreasecrossover point

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items

Reductions for non-clausal theorem proving ⋮ A prover dealing with nominals, binders, transitivity and relation hierarchies ⋮ Complexity-theoretic models of phase transitions in search problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• On the greedy algorithm for satisfiability
• Solving propositional satisfiability problems
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Many hard examples for resolution
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving