Journal of Logic and Computation, Volume 9, Issue 4, pp. 501-513: Abstract.
The probability of pure literals
JW Rosenthal1, JM Plotkin2 and J Franco3
1Department of Mathematics and Computer Science, Ithaca College, Ithaca, NY 14850, USA, E-mail: email@example.com, 2Department of Mathematics, Michigan State University, East Lansing, MI 48824, USA, E-mail: firstname.lastname@example.org, 3Department of Computer Science, University of Cincinnati, Cincinnati, OH 45221, USA, E-mail: email@example.com
We describe an error in earlier probabilistic analyses of the pure literal heuristic as a procedure for solving the satisfiability problem for sets of k-SAT). All probabilistic analyses are in the constant degree model in which a random instance C of k-SAT consists of m clauses selected independently and uniformly (with replacement) from the set of all k-clauses over n variables. We provide a new analysis for k = 2. Specifically, we show with probability approaching 1 as m goes to [infin] one can apply the pure literal rule repeatedly to a random instance of 2-SAT until the number of clauses is 'small' provided n/m [ge] [lgr] > 1. But if n/m [le] [lgr] < 1 and [egr] < 1/4, with probability approaching 1 if the pure literal rule is applied as often as possible, then at least m[egr] clauses will remain.
Keywords: 2-SAT, constant degree model, Davis-Putnam Procedure, pure literal (heuristic), probability of a pure literal.