A Sufficient and Necessary Condition for Sat Problem
Qiu Hai-ming · Acta Scientiarum Naturalium Universitatis Sunyatseni · 2004
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.