Counting the number of solutions for instances of satisfiability
From MaRDI portal
Publication:2277848
DOI10.1016/0304-3975(91)90315-SzbMath0725.68045MaRDI QIDQ2277848
Publication date: 1991
Published in: Theoretical Computer Science (Search for Journal in Brave)
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
