CNF-Satisfiability Test by Counting and Polynomial Average Time

DOI10.1137/0218026zbMATH Open0674.68034OpenAlexW2050917944MaRDI QIDQ3829072FDOQ3829072

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

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

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)

Cited In (34)

• Average Running Time Analysis of an Algorithm to Calculate the Size of the Union of Cartesian Products
• Community Structure Inspired Algorithms for SAT and #SAT
• Approximate Model Counting via Extension Rule
• Polynomial-average-time satisfiability problems
• On the structure of some classes of minimal unsatisfiable formulas
• Title not available (Why is that?)
• Towards logical operations research -- propositional case
• 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.
• New width parameters for SAT and \#SAT
• Are hitting formulas hard for resolution?
• Exponential Average Time for the Pure Literal Rule
• The Pure Literal Rule and Polynomial Average Time
• Complete on average Boolean satisfiability
• Backdoors into Two Occurrences
• Solving \#SAT using vertex covers
• Inclusion-exclusion for \(k\)-CNF formulas
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A dual algorithm for the satisfiability problem
• The \(Multi\)-SAT algorithm
• Irreducible subcube partitions
• Approximate reasoning with credible subsets
• A rigorous methodology for specification and verification of business processes
• Backdoors to Satisfaction
• Resolving contradictions: A plausible semantics for inconsistent systems
• Solving the satisfiability problem by using randomized approach
• Explaining by evidence
• An average case analysis of a resolution principle algorithm in mechanical theorem proving.
• Satisfiable formulas closed under replacement
• Polynomial time termination and constraint satisfaction tests
• Two approximate algorithms for model counting
• 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)