TOPICS
Search

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

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) (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. https://mathworld.wolfram.com/SatisfiabilityProblem.html

Subject classifications