Journal of Logic and Computation, Volume 9, Issue 4, pp. 501513: Abstract.
The probability of pure literalsJW Rosenthal^{1}, JM Plotkin^{2} and J Franco^{3} ^{1}Department of Mathematics and Computer Science, Ithaca College, Ithaca, NY 14850, USA, Email: rosentha@ithaca.edu, ^{2}Department of Mathematics, Michigan State University, East Lansing, MI 48824, USA, Email: plotkin@math.msu.edu, ^{3}Department of Computer Science, University of Cincinnati, Cincinnati, OH 45221, USA, Email: franco@gauss.ececs.uc.edu
We describe an error in earlier probabilistic analyses of the pure literal heuristic as a procedure for solving the satisfiability problem for sets of kSAT). All probabilistic analyses are in the constant degree model in which a random instance C of kSAT consists of m clauses selected independently and uniformly (with replacement) from the set of all kclauses 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 2SAT 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: 2SAT, constant degree model, DavisPutnam Procedure, pure literal (heuristic), probability of a pure literal.
