Average time analyses of simplified Davis-Putnam procedures

DOI10.1016/0020-0190(82)90110-7MaRDI QIDQ787685zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 1982

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(82)90110-7

zbMATH Keywords

satisfiabilityDavis-Putnam procedurepolynomial average timepure literal rule

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3313427 (Why is no real title available?)
• A machine program for theorem-proving
• An Analysis of Backtracking with Search Rearrangement
• An Average Time Analysis of Backtracking
• Backtrack programming techniques
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem

Cited in

(24)

• A statistical approach to adaptive problem solving
• Polynomial-average-time satisfiability problems
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• The expected complexity of analytic tableaux analyses in propositional calculus. II
• Average complexity of divide-and-conquer algorithms
• A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence
• Probabilistic bounds and algorithms for the maximum satisfiability problem
• The large deviations of the whitening process in random constraint satisfaction problems
• Probabilistic performance of a heurisic for the satisfiability problem
• Reasoning with propositional logic: from SAT solvers to knowledge compilation
• A threshold for unsatisfiability
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• On the IO-complexity and approximation languages
• Results related to threshold phenomena research in satisfiability: Lower bounds
• Solving satisfiability in less than \(2^ n\) steps
• Counting propositional models
• The Multi-SAT algorithm
• Approximate reasoning with credible subsets
• Resolving contradictions: A plausible semantics for inconsistent systems
• Solving the satisfiability problem by using randomized approach
• Exact satisfiability, a natural extension of set partition, and its average case behavior
• An average case analysis of a resolution principle algorithm in mechanical theorem proving.
• Explaining by evidence
• A lower bound for tree resolution

This page was built for publication: Average time analyses of simplified Davis-Putnam procedures

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