Average time analyses of simplified Davis-Putnam procedures
From MaRDI portal
Publication:787685
DOI10.1016/0020-0190(82)90110-7zbMath0529.68065OpenAlexW1969377401MaRDI QIDQ787685
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
Related Items (23)
Resolving contradictions: A plausible semantics for inconsistent systems ⋮ Solving satisfiability in less than \(2^ n\) steps ⋮ A lower bound for tree resolution ⋮ Polynomial-average-time satisfiability problems ⋮ Exact satisfiability, a natural extension of set partition, and its average case behavior ⋮ The expected complexity of analytic tableaux analyses in propositional calculus. II ⋮ An average case analysis of a resolution principle algorithm in mechanical theorem proving. ⋮ A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence ⋮ On the IO-complexity and approximation languages ⋮ Average complexity of divide-and-conquer algorithms ⋮ Probabilistic performance of a heurisic for the satisfiability problem ⋮ A statistical approach to adaptive problem solving ⋮ Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem ⋮ Probabilistic bounds and algorithms for the maximum satisfiability problem ⋮ The \(Multi\)-SAT algorithm ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Approximate reasoning with credible subsets ⋮ Solving the satisfiability problem by using randomized approach ⋮ Counting propositional models ⋮ Results related to threshold phenomena research in satisfiability: Lower bounds ⋮ A threshold for unsatisfiability ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Explaining by evidence
Cites Work
This page was built for publication: Average time analyses of simplified Davis-Putnam procedures
