В теории сложности вычислений теорема Кука - Левина, также известная как теорема Кука, утверждает, что проблема булевой выполнимости является NP-полной.
Важным следствием теоремы является то, что если существует детерминированный алгоритм с полиномиальным временем для решения булевой выполнимости, то существует детерминированный алгоритм с полиномиальным временем для решения всех задач в NP.