Изменения
Нет описания правки
===Доказательство принадлежности <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>.
