The Upper Bound Research for Random MAX k-SAT
XU Xue-lin · Journal of Jiangxi Normal University · 2011
Given a CNF formula with n variables and m = αn k-clauses,it is interesting to study the maximum number max Fk of clauses satisfied by all the assignments of the variables(MAX k-SAT).When α is large,the upper bound of f k(n,α n) E(max Fk) for random MAX k-SAT had been derived by the first-moment argument.A tighter upper bound(1-1/2 k)α n + h(α,t)·αn is proved,which is finished also by the first-moment argument and the precision of amplification is improved.At the same time,it is found that the upper bound becomes tighter with the increase of t.