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