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