Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem

DOI10.1016/0166-218X(87)90032-1zbMath0617.68046OpenAlexW2055638404MaRDI QIDQ1822244

John W. Rosenthal, J. M. Plotkin, John V. Franco

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(87)90032-1

zbMATH Keywords

probabilistic analysisNP-completenesssatisfiability problemDavis-Putnam procedureinstance distributionspolynomial average complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

The expected complexity of analytic tableaux analyses in propositional calculus. II ⋮ Probabilistic performance of a heurisic for the satisfiability problem ⋮ Results related to threshold phenomena research in satisfiability: Lower bounds ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon

Cites Work

• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem

This page was built for publication: Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem