Setting 2 Variables at a Time Yields a New Lower Bound for Random 3-SAT
Dimitris Achlioptas · 1999
Let X be a set of n Boolean variables and denote by C(X) be the set of all 3-clauses over X , i.e. the set of all 8 n 3 possible disjunctions of three distinct, non-complementary literals of variables in X . Let F (n; m) be a random 3-SAT formula formed by selecting, with replacement, m clauses uniformly at random from C(X) and taking their conjunction. Finally, let us say that a sequence of events En occurs with high probability (w.h.p.) if lim n!1 Pr[E n ] = 1. The satisfiability threshold conjecture asserts that there exists a constant r 3 such that F (n; rn) is w.h.p. satis able for r r 3 . Experimental evidence suggests r 3 4:2. We prove r 3 > 3:145 improving over the previous best lower bound r 3 > 3:003 due to Frieze and Suen. For this, we introduce a new satisfiability heuristic and analyze its performance. The framework we develop for the analysis of our heuristic allows us to recover most of the previous lower bounds along...