A fast deterministic algorithm for formulas that have many satisfying assignments

DOI10.1093/jigpal/6.1.59zbMath0897.03043OpenAlexW1999002596MaRDI QIDQ4380447

Edward A. Hirsch

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

zbMATH Keywords

deterministic algorithmsatisfying assignment for a Boolean formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (7)

A Short Implicant of a CNF Formula with Many Satisfying Assignments ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ A quantum differentiation ofk-SAT instances ⋮ A short implicant of a CNF formula with many satisfying assignments ⋮ Variable Influences in Conjunctive Normal Forms ⋮ Solving and sampling with many solutions ⋮ Solving and sampling with many solutions: Satisfiability and other hard problems

This page was built for publication: A fast deterministic algorithm for formulas that have many satisfying assignments