Meanings
proper nounthe Cook-Levin theorem
- computingA theorem stating that the Boolean satisfiability problem is NP-complete.
Synonyms: Cook's theorem
Synonyms & antonyms
proper nounA theorem stating that the Boolean satisfiability problem is NP-complete.
Similar
Also see
Origin
Named after Stephen Cook and Leonid Levin.
Full word history & related roots →Cite this entry
APA
Cook-Levin theorem. (n.d.). In WatkinsX Dictionary. Retrieved November 3, 2026, from https://dictionary.watkinsx.com/word/Cook-Levin%20theorem
MLA
“Cook-Levin theorem.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/Cook-Levin%20theorem. Accessed November 3, 2026.
Chicago
WatkinsX Dictionary, s.v. “Cook-Levin theorem,” accessed November 3, 2026, https://dictionary.watkinsx.com/word/Cook-Levin%20theorem.
Source: Cook-Levin theorem on Wiktionary, CC BY-SA 4.0.