On the Maximum Satisfiability of Random Formulas

Maximum satisfiability is a canonical NP-hard optimization problem that appears empirically hard for random instances. Let us say that a Conjunctive normal form (CNF) formula consisting of k-clauses is p-satisfiable if there exists a truth assignment satisfying 1−2−k+p2−k of all clauses (observe that every k-CNF is 0-satisfiable). Also, let Fk(n,m) denote a random k-CNF on nvariables formed by selecting uniformly and independently m out of all possible k-clauses. It is easy to prove that for every k>1 and every p in (0,1], there is Rk(p) such that if r>Rk(p), then the probability that Fk(n,rn) is p-satisfiable tends to 0 as n tends to infinity. We prove that there exists a sequence δk→0 such that if r<(1−δk)Rk(p) then the probability that Fk(n,rn)is p-satisfiable tends to 1 as n tends to infinity. The sequence δk tends to 0 exponentially fast in k.