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归约等价的.

关键词：极小不可满足公式、归约、MAX-k-SAT问题、PTAS等价

所属期刊栏目：3

分类号：TP301(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant No.60863005,60911130013

在线出版日期：2010-01-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：641-648