The Pure Literal Rule and Polynomial Average Time

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

zbMATH Keywords

satisfiability problemsearchingbacktrackingpure literal ruleaverage timesimplified version of the Davis-Putnam procedure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

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