On the maximum satisfiability of random formulas
Dimitris Achlioptas, Assaf Naor, Yuval Peres · Journal of the ACM · 2007
Say that a k -CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 − 2 − k + p 2 − k of its clauses (note that every k -CNF formula is 0-satisfiable). Let F k ( n , m ) denote a random k -CNF formula on n variables with m clauses. For every k ≥2 and every r >0 we determine p and δ=δ( k )= O ( k 2 − k /2 ) such that with probability tending to 1 as n →∞, a random k -CNF formula F k ( n , rn ) is p -satisfiable but not ( p +δ)-satisfiable.