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.
Satisfiability Problem
See also
Boolean Algebra, SatisfiableExplore 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 ProblemCite this as:
Weisstein, Eric W. "Satisfiability Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SatisfiabilityProblem.html