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

• 作者: 王晓峰 许道云
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 极小不可满足性 正则(3,4)-CNF公式 NP-完全性 不可近似性
• 年，卷（期）: 2013,（8）
• 所属期刊栏目: 学术研究
• 页码范围: 691-697
• 页数: 7页
• 分类号: TP301
• 字数: 6452字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1305025

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学系	125	460	12.0	16.0
2	王晓峰	贵州大学计算机科学系	26	122	6.0	9.0