On the Maximum Satisfiability of Random Formulas

الأصل · EN

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⁻ᵏ+p 2⁻ᵏ of all clauses (observe that every k-CNF is 0-satisfiable). Also, let Fₖ(n,m) denote a random k-CNF on n variables 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 Rₖ(p) such that if r >Rₖ(p), then the probability that Fₖ(n,rn) is p-satisfiable tends to 0 as n tends to infinity. We prove that there exists a sequence δₖ → 0 such that if r <(1-δₖ) Rₖ(p) then the probability that Fₖ(n,rn)is p-satisfiable tends to 1 as n tends to infinity. The sequence δₖ tends to 0 exponentially fast in k.