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, Satisfiable

Explore with Wolfram|Alpha


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) (Ed. D. Du, J. Gu, and P. M. Pardalos). Providence, RI: Amer. Math. Soc., pp. 1-17, 1997.

Referenced on Wolfram|Alpha

Satisfiability Problem

Cite this as:

Weisstein, Eric W. "Satisfiability Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications