CNF-Satisfiability Test by Counting and Polynomial Average Time

DOI10.1137/0218026MaRDI QIDQ3829072zbMATH OpenOpenAlexFDO

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

(39)

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

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)