Probabilistic performance of a heurisic for the satisfiability problem

DOI10.1016/0166-218X(88)90121-7zbMath0663.68059MaRDI QIDQ1115189

Yuan Chuan Ho, John V. Franco

Publication date: 1988

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

zbMATH Keywords

probabilistic analysisNP-completesatisfiabilityaverage analysisDavis-Putnam

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05)

Related Items (4)

Complete on average Boolean satisfiability ⋮ Solving the satisfiability problem by using randomized approach ⋮ Results related to threshold phenomena research in satisfiability: Lower bounds ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon

Cites Work

• Unnamed Item
• Average time analyses of simplified Davis-Putnam procedures
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• On the complexity of regular resolution and the Davis-Putnam procedure
• Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• The Pure Literal Rule and Polynomial Average Time
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• A Computing Procedure for Quantification Theory

This page was built for publication: Probabilistic performance of a heurisic for the satisfiability problem