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