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