Изменения
Нет описания правки
# <tex> 3SAT \in NPH </tex>;
===Доказательство принадлежности <tex>3SAT</tex> классу <tex>NP</tex>===
Возьмем в качестве сертификата набор <tex>x_1 \ldots x_{n}</tex>, где <tex>x_i \in \{0,1\}</tex>.
Верификатор подставляет <tex>x_1 \ldots x_n</tex> в формулу и проверяет её на равенство единице.
Время работы верификатора и длина сертификата, очевидно, полиномиальны. Итак, <tex>3SAT \in NP</tex>.
===Доказательство принадлежности <tex>3SAT</tex> классу <tex>NPH</tex>===
Покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> сводится по Куку к <tex>3SAT</tex>.
