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