A fast deterministic algorithm for formulas that have many satisfying assignments
From MaRDI portal
Publication:4380447
DOI10.1093/jigpal/6.1.59zbMath0897.03043MaRDI QIDQ4380447
Publication date: 17 March 1998
Published in: Logic Journal of IGPL (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/cb16dd1d1e87fcac630b941febd836a22aed6f56
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
Related Items
A quantum differentiation ofk-SAT instances, Solving and sampling with many solutions: Satisfiability and other hard problems, Counting Solutions to Polynomial Systems via Reductions, A short implicant of a CNF formula with many satisfying assignments, Solving and sampling with many solutions, A Short Implicant of a CNF Formula with Many Satisfying Assignments, Variable Influences in Conjunctive Normal Forms