Изменения
Нет описания правки
# <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>(x)</tex>, <tex>(x \vee y)</tex>, <tex>(x_1 \vee x_{2} \vee \ldots \vee x_{m})</tex> к нужному виду.
