Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
Dimitris Achlioptas · 2000
Let X be a set of n Boolean variables and denote by C(X) the set of all 3-clauses over X, i.e. the set of all 8(3) possible disjunctions of three distinct, non-complementary literais from 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. The satisfiability threshold conjecture asserts that there exists a constant ra such that as n--+ c¢, F(n, rn) is satisfiable with probability that tends to 1 if r r3. Experimental evidence suggests rz ~ 4.2. We prove rz> 3.145 improving over the previous best lower bound r3> 3.003 due to Frieze and Suen. For this, we intro-duce a satisfiability heuristic that works iteratively, permanently setting the value of a pair of variables in each round. The framework we develop for the analysis of our heuristic allows us to also derive most previous lower bounds for random 3-SAT in a uniform manner and with little effort.