Number of models and satisfiability of sets of clauses

DOI10.1016/0304-3975(95)00144-1zbMath0873.68094OpenAlexW2036350017WikidataQ127840271 ScholiaQ127840271MaRDI QIDQ672138

Wen-Hui Zhang

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00144-1

zbMATH Keywords

satisfiability3-SAT problemspropositional formulas represented by sets of clauses

Mathematics Subject Classification ID

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

Related Items (12)

New upper bound for the \#3-SAT problem ⋮ Counting for satisfiability by inverting resolution ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances ⋮ New methods for 3-SAT decision and worst-case analysis ⋮ On \(k\)-positive satisfiability problem ⋮ Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT ⋮ Faster exponential-time algorithms for approximately counting independent sets ⋮ Counting models for 2SAT and 3SAT formulae ⋮ A rigorous methodology for specification and verification of business processes ⋮ A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. ⋮ Explaining by evidence

Cites Work

• Solving satisfiability in less than \(2^ n\) steps
• The relative efficiency of propositional proof systems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Number of models and satisfiability of sets of clauses