Number of models and satisfiability of sets of clauses

DOI10.1016/0304-3975(95)00144-1zbMATH Open0873.68094OpenAlexW2036350017WikidataQ127840271 ScholiaQ127840271MaRDI QIDQ672138FDOQ672138

Authors: Wenhui 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

Recommendations

• Counting the number of solutions for instances of satisfiability
• On Random 3-sat
• Counting models for 2SAT and 3SAT formulae
• scientific article; zbMATH DE number 515744
• scientific article; zbMATH DE number 2090009

zbMATH Keywords

satisfiability3-SAT problemspropositional formulas represented by sets of clauses

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The relative efficiency of propositional proof systems
• Title not available (Why is that?)
• Solving satisfiability in less than \(2^ n\) steps
• Title not available (Why is that?)

Cited In (14)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672138)