| 一个SAT问题有解的充要条件 |
| |
| 引用本文： | 余丰人,丘海明.一个SAT问题有解的充要条件[J].中山大学学报(自然科学版),2004,43(2):37-39. |
| |
| 作者姓名： | 余丰人 丘海明 |
| |
| 作者单位： | 中山大学电子与通信工程系,广东,广州,510275 |
| |
| 摘 要： | 合取范式可满足性问题(简称SAT问题)是一个NP完全问题.引入了一个饱和合取范式的概念,利用饱和合取范式的性质,对SAT问题的本质进行了研究.在此基础上,证明了一个SAT问题有解的充要条件,它为SAT问题完全算法和非完全快速算法的深入研究提供了一条新的思路.
|
| 关 键 词： | 合取范式 SAT问题 NP完全问题 |
| 文章编号： | 0529-6579(2004)02-0037-03 |
| 修稿时间： | 2003年7月4日 |
A Sufficient and Necessary Condition for Sat Problem |
| |
| YU Feng-ren,QIU Hai-ming.A Sufficient and Necessary Condition for Sat Problem[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2004,43(2):37-39. |
| |
| Authors: | YU Feng-ren QIU Hai-ming |
| |
| Abstract: | The satisfiability problem of conjunction normal form (abbreviate SAT problem) is an NP_complete problem.An new concept of saturated conjunctive normal form is introduced and the nature of SAT problem is studied for utilizing the characteristic of saturated conjunctive normal form.Based on the sufficient and necessary condition for SAT problem,a new idea is provided for further study of the complete algorithm and non_complete fast algorithm of SAT problem. |
| |
| Keywords: | conjunction normal form SAT problem NP-complete problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
