Satisfiability problem: Some polynomial classes of conjunctive normal forms

摘要

The NP-complete problem of satisfiability of conjunctive normal forms (CNF) is considered. Necessary and sufficient conditions of CNF satisfiability are derived and some polynomial classes of CNF are identified.