Complete on average Boolean satisfiability
From MaRDI portal
Publication:1872642
DOI10.1006/jcom.2002.0649zbMath1016.68043OpenAlexW1990466738MaRDI QIDQ1872642
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
satisfiabilityCNF formulasaverage NP-completenessdistributional Booleandistributional tilingdynamic binary coding schemerandomized reductions.
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