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

A Complexity Analysis on SAT Problem

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

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.