Home  Online Resources  Table of Contents

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: rosentha@ithaca.edu, 2Department of Mathematics, Michigan State University, East Lansing, MI 48824, USA, E-mail: plotkin@math.msu.edu, 3Department of Computer Science, University of Cincinnati, Cincinnati, OH 45221, USA, E-mail: 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 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.

  Full-Text PDF  (152 KB)

[ Oxford University Press]   [ Oxford Journals]   [ Comments & Feedback]   Copyright© Oxford University Press, 1999.