Setting 2 Variables at a Time Yields a New Lower Bound for Random 3-SAT

摘要: Let X be a set of n Boolean variables and denote by C(X) the all 3-clauses over X, i.e. 8 ( 3 ) possible disjunctions three distinct, non-complementary literals in X. F (n,m) random 3-SAT formula formed selecting, with replacement, m clauses uniformly at from taking their conjunction. Finally, let us say that sequence events En occurs high probability (w.h.p.) if limn→∞ Pr[En] = 1. The satisfiability threshold conjecture asserts there exists constant r3 such (n, rn) is w.h.p. satisfiable for r r3. Experimental evidence suggests ≈ 4.2. We prove > 3.145 improving previous best lower bound 3.003 due to Frieze Suen. For this, we introduce new heuristic analyze its performance. framework develop analysis our allows recover most bounds along uniform manner little additional effort.