теория-алгоритмов - Логика высказываний

Если формула выполнима, то существует выполняющая оценка. Проверка того, что она подходит, занимает полиномиальное (линейное) время. Следовательно, задача нахождения такой оценки (если она есть), принадлежит классу NP. Если P=NP, то для этой же задачи имеется детерминистский алгоритм, решающий её за полиномиальное время. Допустим, что ответ отрицателен -- тогда всё сделано. При положительном ответе остаётся найти выполняющую оценку. Полагаем первую переменную x1 равной 0, подставляем в формулу. Проверяем её при помощи того же полиномиального алгоритма на выполнимость. В случае положительного ответа оставляем значение x1=0, в случае отрицательного берём x1=1. Формула с выбранным значением x1 выполнима, и далее то же делаем с переменной x2. За n шагов мы найдём выполняющую оценку, а время работы алгоритма останется полиномиальным, будучи умноженным на O(n).