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