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