| 关于合取范式可满足性问题的复杂性分析 |
| |
| 引用本文： | 余丰人,丘海明. 关于合取范式可满足性问题的复杂性分析[J]. 中山大学学报(自然科学版), 2006, 45(2): 121-122 |
| |
| 作者姓名： | 余丰人 丘海明 |
| |
| 作者单位： | 中山大学电子与通信工程系,广东,广州,510275 |
| |
| 摘 要： | 合取范式可满足性问题(简称SAT问题)是典型的NP完全问题,本文引入了一个饱和子句集的新概念,利用饱和子句集的特性,研究了SAT问题的复杂性,证明了SAT问题复杂性为多项式的一个充分条件,并揭示了二元可满足性问题与三元可满足性问题的本质差别。因此,通过变换来提炼出SAT问题的复杂性的本质特征,并加以研究的方法,是SAT问题的复杂性研究的一种有效方法。
|
| 关 键 词： | 合取范式 SAT问题 复杂性分析 |
| 文章编号： | 0529-6579（2006）02-0121-02 |
| 收稿时间： | 2005-05-01 |
| 修稿时间： | 2005-05-01 |
A Complexity Analysis on SAT Problem |
| |
| Yu Feng-ren,Qiu Hai-ming. A Complexity Analysis on SAT Problem[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2006, 45(2): 121-122 |
| |
| Authors: | Yu Feng-ren Qiu Hai-ming |
| |
| Affiliation: | Department of Electronics and Communication Engineering, Sun Yat-sen University, Guangzhou 510275, China |
| |
| Abstract: | The satisfiability of conjunction normal form(abbreviate SAT problem) is a typical NP-complete problem.To study the complexity of SAT problem,a new concept of saturated clause muster has been introduced with using the characteristic of saturated clause muster.The sufficient condition of SAT problem was approved to be a polynomial and has opened out essential distinction of 2SAT and 3SAT problems.In conclusion,it will be a effective method for the study of the complexity of SAT problem to abstract the essential characters of the complexity of SAT problem through transform. |
| |
| Keywords: | conjunction normal form SAT problem complexity analysis |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
