info prev up next book cdrom email home

Satisfiability Problem

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


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 Eric W. Weisstein