CNF-Satisfiability Test by Counting and Polynomial Average Time

DOI10.1137/0218026zbMATH Open0674.68034OpenAlexW2050917944MaRDI QIDQ3829072FDOQ3829072

Authors Kazuo Iwama

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

zbMATH Keywords

backtrackingindependent setsaverage timeCNF SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Polynomial-average-time satisfiability problems
• scientific article; zbMATH DE number 1555929
• Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms
• The Pure Literal Rule and Polynomial Average Time
• Exponential Average Time for the Pure Literal Rule

Cited in

(35)

• Are hitting formulas hard for resolution?
• scientific article; zbMATH DE number 4049072 (Why is no real title available?)
• Backdoors to satisfaction
• Resolving contradictions: A plausible semantics for inconsistent systems
• A rigorous methodology for specification and verification of business processes
• Satisfiable formulas closed under replacement
• The Pure Literal Rule and Polynomial Average Time
• Exponential Average Time for the Pure Literal Rule
• A dual algorithm for the satisfiability problem
• Solving the satisfiability problem by using randomized approach
• scientific article; zbMATH DE number 799949 (Why is no real title available?)
• An average case analysis of a resolution principle algorithm in mechanical theorem proving.
• Polynomial time termination and constraint satisfaction tests
• Approximate reasoning with credible subsets
• Solving \#SAT using vertex covers
• On the structure of some classes of minimal unsatisfiable formulas
• Complete on average Boolean satisfiability
• The \(Multi\)-SAT algorithm
• Towards logical operations research -- propositional case
• scientific article; zbMATH DE number 1555929 (Why is no real title available?)
• Average running time analysis of an algorithm to calculate the size of the union of Cartesian products.
• Irreducible subcube partitions
• scientific article; zbMATH DE number 4060775 (Why is no real title available?)
• Polynomial-average-time satisfiability problems
• New width parameters for SAT and \#SAT
• Solving MAX-\(r\)-SAT above a tight lower bound
• Average Running Time Analysis of an Algorithm to Calculate the Size of the Union of Cartesian Products
• Inclusion-exclusion for \(k\)-CNF formulas
• Approximate model counting via extension rule
• Counting for satisfiability by inverting resolution
• Two approximate algorithms for model counting
• Community structure inspired algorithms for SAT and \#SAT
• Backdoors into two occurrences
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Explaining by evidence

This page was built for publication: CNF-Satisfiability Test by Counting and Polynomial Average Time

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