|statement= Пусть <tex>SAT \in P </tex>, тогда для любой формулы <tex>\phi \in SAT</tex> можно за полиномиальное время вывести набор значений, удовлетворяющий формуле.
|proof=
В случае если Если <tex>\phi</tex> не содержит переменных, то есть является тождественной единицей, решение задачи тривиально.Выберем Иначе, выберем любую переменную <tex>x</tex> из формулы <tex>\phi</tex>, и выполним подстановку <tex>x = 0</tex>. Получим формулу <tex>\phi_0</tex>. Если <tex>\phi_0 \in SAT</tex> (по условию теоремы, проверку можно выполнить за полиномиальное время), то мы свели задачу к задаче аналогичной с меньшим числом переменных. В противном случае, сведение выполняется подстановкой <tex>x = 1</tex>.
}}
