关于合取范式可满足性问题的复杂性分析

• 作者: 丘海明 余丰人
• 来源期刊: 中山大学学报（自然科学版）
• 学科: 工学
• 关键词: 合取范式 SAT问题 复杂性分析
• 年，卷（期）: 2006,（2）
• 所属期刊栏目: 研究简报
• 页码范围: 121-122
• 页数: 2页
• 分类号: TN711.1
• 字数: 1864字
• 语种: 中文
• DOI: 10.3321/j.issn:0529-6579.2006.02.029

摘要

合取范式可满足性问题(简称SAT问题)是典型的NP完全问题,本文引入了一个饱和子句集的新概念,利用饱和子句集的特性,研究了SAT问题的复杂性,证明了SAT问题复杂性为多项式的一个充分条件,并揭示了二元可满足性问题与三元可满足性问题的本质差别.因此,通过变换来提炼出SAT问题的复杂性的本质特征,并加以研究的方法,是SAT问题的复杂性研究的一种有效方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	余丰人	中山大学电子与通信工程系	5	10	2.0	3.0
2	丘海明	中山大学电子与通信工程系	10	64	4.0	8.0