A fast deterministic algorithm for formulas that have many satisfying assignments

DOI10.1093/JIGPAL/6.1.59MaRDI QIDQ4380447zbMATH OpenOpenAlexFDO

Authors Edward A. Hirsch

Publication date 17 March 1998

Published in Logic Journal of the 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)

Recommendations

• A short implicant of a CNF formula with many satisfying assignments
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• A short implicant of a CNF formula with many satisfying assignments
• Why almost all satisfiable k-CNF formulas are easy
• A better algorithm for random \(k\)-SAT

Cited in

(9)

• A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula
• A short implicant of a CNF formula with many satisfying assignments
• Solving and sampling with many solutions
• Solving and sampling with many solutions: satisfiability and other hard problems
• A quantum differentiation of k-SAT instances
• Counting solutions to polynomial systems via reductions
• Variable Influences in Conjunctive Normal Forms
• A short implicant of a CNF formula with many satisfying assignments
• On finding and detecting efficient assignments in the case of multiple inputs and outputs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4380447)