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.

**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.

© 1996-9

1999-05-26