The Pure Literal Rule and Polynomial Average Time

DOI10.1137/0214067zbMath0575.68060MaRDI QIDQ3694704

Paul Walton jun. Purdom, Cynthia A. Brown

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 problem; searching; backtracking; pure literal rule; average time; simplified version of the Davis-Putnam procedure

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

Related Items

Approximate reasoning with credible subsets, Explaining by evidence, Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem, Polynomial-average-time satisfiability problems, An exponential lower bound for the pure literal rule, Probabilistic performance of a heurisic for the satisfiability problem, Solving the satisfiability problem by using randomized approach, Counting propositional models, On the occurence of null clauses in random instances of Satisfiability, Resolving contradictions: A plausible semantics for inconsistent systems, Easy problems are sometimes hard, 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., The \(Multi\)-SAT algorithm