关于随机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的增大而变得更紧.

MAX-k-SAT的PTAS归约等价性

通过构造适当的极小不可满足公式,利用子句拼接技术,引入了一个一般化的从k-CNF公式(k≥3)到3-CNF公式之间的归约转换。基于该转换,给出了一个真值指派的转换算法,并证明了MAX-k-SAT与MAX-3-SAT是PTAS归约等价的。因此,对于k,t≥3,MAX-k-SAT与MAX-t-SAT是PTAS归约等价的。