SAT
← Back to NP-Complete
The Boolean Satisfiability Problem: determine whether there exists an assignment of truth values that makes a Boolean formula true. The first problem proven NP-Complete (Cook-Levin theorem, 1971). The foundation for all NP-completeness proofs via reduction.