The Pure Literal Rule and Polynomial Average Time
From MaRDI portal
Publication:3694704
DOI10.1137/0214067zbMath0575.68060OpenAlexW2016042296MaRDI QIDQ3694704
Cynthia A. Brown, Paul Walton jun. Purdom
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214067
satisfiability problemsearchingbacktrackingpure literal ruleaverage timesimplified version of the Davis-Putnam procedure
Related Items
Resolving contradictions: A plausible semantics for inconsistent systems ⋮ Easy problems are sometimes hard ⋮ Polynomial-average-time satisfiability problems ⋮ 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. ⋮ An exponential lower bound for the pure literal rule ⋮ Probabilistic performance of a heurisic for the satisfiability problem ⋮ Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem ⋮ The \(Multi\)-SAT algorithm ⋮ Approximate reasoning with credible subsets ⋮ Solving the satisfiability problem by using randomized approach ⋮ Counting propositional models ⋮ On the occurence of null clauses in random instances of Satisfiability ⋮ Explaining by evidence