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

average timebacktrackingCNF SATindependent sets

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

(41)

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

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)