Counting the number of solutions for instances of satisfiability

DOI10.1016/0304-3975(91)90315-SzbMath0725.68045MaRDI QIDQ2277848

Olivier Dubois

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (20)

A kind of logical compilation for knowledge bases ⋮ New upper bound for the \#3-SAT problem ⋮ Counting for satisfiability by inverting resolution ⋮ A bright side of NP-hardness of interval computations: Interval heuristics applied to NP-problems ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances ⋮ OuterCount: a first-level solution-counter for quantified Boolean formulas ⋮ Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT ⋮ The scaling window of the 2-SAT transition ⋮ A natural explanation for the minimum entropy production principle ⋮ Faster exponential-time algorithms for approximately counting independent sets ⋮ The incremental satisfiability problem for a two conjunctive normal form ⋮ On the greedy algorithm for satisfiability ⋮ Counting models for 2SAT and 3SAT formulae ⋮ Using binary patterns for counting falsifying assignments of conjunctive forms ⋮ A threshold for unsatisfiability ⋮ A rigorous methodology for specification and verification of business processes ⋮ Entropy of theK-Satisfiability Problem ⋮ Probabilistic approach to the satisfiability problem ⋮ Explaining by evidence

Cites Work

• Unnamed Item
• Unnamed Item
• A simplified NP-complete satisfiability problem
• Probabilistic approach to the satisfiability problem
• Uniquely solvable quadratic Boolean equations
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• On the unique satisfiability problem
• The Complexity of Enumeration and Reliability Problems
• On the Complexity of Timetable and Multicommodity Flow Problems

This page was built for publication: Counting the number of solutions for instances of satisfiability