Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
From MaRDI portal
Publication:1822244
DOI10.1016/0166-218X(87)90032-1zbMath0617.68046MaRDI QIDQ1822244
John W. Rosenthal, J. M. Plotkin, John V. Franco
Publication date: 1987
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
probabilistic analysis; NP-completeness; satisfiability problem; Davis-Putnam procedure; instance distributions; polynomial average complexity
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Results related to threshold phenomena research in satisfiability: Lower bounds, Probabilistic performance of a heurisic for the satisfiability problem, The expected complexity of analytic tableaux analyses in propositional calculus. II, Typical case complexity of satisfiability algorithms and the threshold phenomenon
Cites Work