摘要
合取范式可满足性问题(简称SAT问题)是一个NP完全问题。引入了一个饱和合取范式的概念,利用饱和合取范式的性质,对SAT问题的本质进行了研究。在此基础上,证明了一个SAT问题有解的充要条件,它为SAT问题完全算法和非完全快速算法的深入研究提供了一条新的思路。
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.
出处
《中山大学学报（自然科学版）》
CAS
CSCD
北大核心
2004年第2期37-39,共3页
Acta Scientiarum Naturalium Universitatis Sunyatseni
基金
广东省自然科学基金重点项目资助(021753)
关键词
合取范式
SAT问题
NP完全问题
conjunction normal form
SAT problem
NP-complete problem
