CNF-Satisfiability Test by Counting and Polynomial Average Time
From MaRDI portal
Publication:3829072
DOI10.1137/0218026zbMath0674.68034OpenAlexW2050917944MaRDI QIDQ3829072
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218026
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items
Resolving contradictions: A plausible semantics for inconsistent systems, Approximate Model Counting via Extension Rule, Community Structure Inspired Algorithms for SAT and #SAT, Backdoors to Satisfaction, An average case analysis of a resolution principle algorithm in mechanical theorem proving., Counting for satisfiability by inverting resolution, Unnamed Item, Are hitting formulas hard for resolution?, Irreducible subcube partitions, On the structure of some classes of minimal unsatisfiable formulas, Average running time analysis of an algorithm to calculate the size of the union of Cartesian products., Solving MAX-\(r\)-SAT above a tight lower bound, The \(Multi\)-SAT algorithm, Solving \#SAT using vertex covers, Approximate reasoning with credible subsets, New width parameters for SAT and \#SAT, Solving the satisfiability problem by using randomized approach, Two approximate algorithms for model counting, Towards logical operations research -- propositional case, Inclusion-exclusion for \(k\)-CNF formulas, A dual algorithm for the satisfiability problem, A rigorous methodology for specification and verification of business processes, Backdoors into Two Occurrences, Average Running Time Analysis of an Algorithm to Calculate the Size of the Union of Cartesian Products, Explaining by evidence
