| k-LSAT (k≥3)是NP-完全的 |
| |
| 引用本文： | 许道云,邓天炎,张庆顺.k-LSAT (k≥3)是NP-完全的[J].软件学报,2008,19(3):511-521. |
| |
| 作者姓名： | 许道云 邓天炎 张庆顺 |
| |
| 作者单位： | 贵州大学 计算机科学系,贵州 贵阳 550025;贵州大学 计算机科学系,贵州 贵阳 550025;贵州大学 计算机科学系,贵州 贵阳 550025 |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant Nos.10410638,60310213(国家自然科学基金) |
| |
| 摘 要： | 合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的.LCNF≥k是子句长度大于或等于k的CNF公式子类,判定问题LSA(≥k)的NP-完全性与LCNF(≥k)中是否含有不可满足公式密切相关.即LSAT≥k的NP-完全性取决于LCNF≥k是否含有不可满足公式.S.Porschen等人用超图和拉丁方的方法构造了LCNF≥3和LCNF≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.
|
| 关 键 词： | 线性CNF公式 不可满足性 NP-完全性 极小不可满足公式 归约 |
| 收稿时间： | 2006-12-13 |
| 修稿时间： | 2007-01-24 |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
