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

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

Review text

How can we find any satisfying assignment for a Boolean formula that has many satisfying assignments? This paper presents a polynomial-time deterministic algorithm that solves this problem and shows that its worst-case running time is linear when input formulas are in \(\kappa\)-CNF and a fraction of satisfying assignments is greater than a constant. Another result: if a formula in \(\kappa\)-CNF has many satisfying assignments, then there exists a short satisfying assignment.

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

(10)

• A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula
• Solving and sampling with many solutions
• 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
• Variable Influences in Conjunctive Normal Forms
• 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
• A short implicant of a CNF formula with many satisfying assignments
• Algorithms for the diverse-k-SAT problem: the geometry of satisfying assignments

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)