Average time analyses of simplified Davis-Putnam procedures

DOI10.1016/0020-0190(82)90110-7zbMATH Open0529.68065OpenAlexW1969377401MaRDI QIDQ787685FDOQ787685

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• A machine program for theorem-proving
• Backtrack programming techniques
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• An Analysis of Backtracking with Search Rearrangement
• An Average Time Analysis of Backtracking

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
• A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence
• Average complexity of divide-and-conquer algorithms
• Probabilistic bounds and algorithms for the maximum satisfiability problem
• The large deviations of the whitening process in random constraint satisfaction problems
• Reasoning with propositional logic: from SAT solvers to knowledge compilation
• Probabilistic performance of a heurisic for the satisfiability problem
• A threshold for unsatisfiability
• Results related to threshold phenomena research in satisfiability: Lower bounds
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• On the IO-complexity and approximation languages
• 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
• Explaining by evidence
• 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.
• 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)