一个正则NP-完全问题及其不可近似性

摘要：

通过一个适当的归约变换,可以将一个CNF (conjunctive normal form)公式变换为另一个具有某种特殊结构或性质的公式,使两者具有相同的可满足性.带有正则结构的CNF公式的因子图在图论中具有某些良好的性质和结果,可以用于研究公式的可满足性和计算复杂性.极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足.借助此临界特性,给出了一个从3-CNF公式到正则(3,4)-CNF公式的多项式归约转换.这里,正则(3,4)-CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4.因此,正则(3,4)-SAT问题是一个NP-完全问题,并且MAX(3,4)-SAT是不可近似问题.

关键词：极小不可满足性、正则(3,4)-CNF公式、NP-完全性、不可近似性

所属期刊栏目：7

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

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

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

页数：共7页

页码：691-697