Complete on average Boolean satisfiability

DOI10.1006/jcom.2002.0649zbMath1016.68043OpenAlexW1990466738MaRDI QIDQ1872642

Jie Wang

Publication date: 14 May 2003

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.2002.0649

zbMATH Keywords

satisfiabilityCNF formulasaverage NP-completenessdistributional Booleandistributional tilingdynamic binary coding schemerandomized reductions.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic performance of a heurisic for the satisfiability problem
• Average case completeness
• On the theory of average case complexity
• Randomizing Reductions of Search Problems
• Many hard examples for resolution
• Average Case Complete Problems
• Distributional Word Problem for Groups
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: Complete on average Boolean satisfiability