关于随机MAX k-SAT模型的上界研究

The Upper Bound Research for Random MAX k-SAT

对于包含n个变量和m=αn个长度为k的子句的CNF公式,人们比较关注公式中最大可满足子句的个数max Fk(MAX k-SAT).当子句密度α比较大时,随机MAX k-SAT模型中的变量f k(n,αn)E(max Fk)的上界可以用一阶矩方法给出.通过对一阶矩方法放缩精度的改进,得到了它的一个更紧的上界(1-1/2 k)αn+h(α,t)·αn.同时,可以证明这个新的上界随着t的增大而变得更紧.

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.