k-LSAT(k≥3)是NP-完全的

• 作者: 张庆顺 许道云 邓天炎
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 线性CNF公式 不可满足性 NP-完全性 极小不可满足公式 归约
• 年，卷（期）: 2008,（3）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 511-521
• 页数: 11页
• 分类号: TP301
• 字数: 5976字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2008.00511

摘要

合取范式(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-完全的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学系	125	460	12.0	16.0
2	张庆顺	贵州大学计算机科学系	3	8	1.0	2.0
3	邓天炎	贵州大学计算机科学系	3	9	1.0	3.0