Counting the number of solutions for instances of satisfiability
We attempt to count the number of solutions of SAT instances by combinatorial formulas. For this a notion of independence between clauses is introduced. A formula for computing the number of solutions of independent clauses in linear time is given. We establish a formula for computing the number of solutions of a set of any clauses. Transformation of a set of any clauses into an equivalent set of independent clauses is proposed. The transformation allows all solutions of a SAT instance to be determined with a time complexity less than \(L2^ n\) (L being the length of the instance), i.e. \(O(kr_{\max}2^{r_{\max}}\alpha^ n_{r_{\max}})\), n being the numbers of variables, k the number of clauses and \(r_{\max}\) the maximum length of clauses (for example for 3-SAT \(\alpha_ 3\approx 1.84)\). Finally, experimental results are provided for variations of number of solutions by number of clauses for random 2-SAT and 3-SAT instances. These experimental results are in agreement with the theoretical results established in \textit{O. Dubois} and \textit{J. Carlier} [Probabilistic approach to the satisfiability problem, Theor. Comput. Sci. 81, 65-76 (1991)] concerning the mathematical expectation of the number of solutions.
- A simplified NP-complete satisfiability problem
- scientific article; zbMATH DE number 3566230 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- On the Complexity of Timetable and Multicommodity Flow Problems
- On the r,s-SAT satisfiability problem and a conjecture of Tovey
- On the unique satisfiability problem
- Probabilistic approach to the satisfiability problem
- The Complexity of Enumeration and Reliability Problems
- Uniquely solvable quadratic Boolean equations
- A rigorous methodology for specification and verification of business processes
- On the greedy algorithm for satisfiability
- A kind of logical compilation for knowledge bases
- The incremental satisfiability problem for a two conjunctive normal form
- Counting models for 2SAT and 3SAT formulae
- A bright side of NP-hardness of interval computations: Interval heuristics applied to NP-problems
- A natural explanation for the minimum entropy production principle
- Faster exponential-time algorithms for approximately counting independent sets
- New upper bound for the \#3-SAT problem
- Counting for satisfiability by inverting resolution
- Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
- Using binary patterns for counting falsifying assignments of conjunctive forms
- The scaling window of the 2-SAT transition
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Enumerating All Solutions for Constraint Satisfaction Problems
- scientific article; zbMATH DE number 69339 (Why is no real title available?)
- scientific article; zbMATH DE number 2084758 (Why is no real title available?)
- Entropy of theK-Satisfiability Problem
- Explaining by evidence
- A threshold for unsatisfiability
- Relation between the hardness of a problem and the number of its solutions
- A note on the use of independent sets for the k-SAT problem
- Algorithms for four variants of the exact satisfiability problem
- OuterCount: a first-level solution-counter for quantified Boolean formulas
- Number of models and satisfiability of sets of clauses
- A graphical \#SAT algorithm for formulae with small clause density
- Counting QBF solutions at level two
- Probabilistic approach to the satisfiability problem
This page was built for publication: Counting the number of solutions for instances of satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277848)
