69
правок
Изменения
Нет описания правки
{{Лемма
|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>.
}}
{{Теорема
|author=Карп, Липтон
