|
|
|
Deciding whether a given Boolean formula in conjunctive normal form has an assignment that makes the formula ``true.'' In 1971, Cook showed that the problem is NP-Complete.
See also Boolean Algebra
References
Cook, S. A. and Mitchell, D. G. ``Finding Hard Instances of the Satisfiability Problem: A Survey.'' In
Satisfiability problem: theory and applications (Piscataway, NJ, 1996).
Theoret. Comput. Sci., Vol. 35. Providence, RI: Amer. Math. Soc., pp. 1-17, 1997.