On the satisfiability and maximum satisfiability of random 3-CNF formulas
Andrei Broder, ALAN M. FRIEZE, Eli Upfal · Symposium on Discrete Algorithms · 1993
We analyze the pure literal rule heuristic for computing a satisfying assignment to a random 3-CNF formula with n variables. We show that the pure literal rule by itself finds satisfying assignments for almost all 3-CNF formulas with up to 1.63n clauses, but it fails for more than 1.7n clauses. As an aside we show that the value of maximum satisfiability for random 3-CNF formulas is tightly concentrated around its mean.