Complete on average Boolean satisfiability
From MaRDI portal
Publication:1872642
DOI10.1006/jcom.2002.0649zbMath1016.68043MaRDI 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
satisfiability; CNF formulas; average NP-completeness; distributional Boolean; distributional tiling; dynamic binary coding scheme; randomized reductions.
68Q25: Analysis of algorithms and problem complexity
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