Изменения
→Доказательство принадлежности классу NP
* <tex> CNFSAT \in NPH </tex>
==== Доказательство принадлежности классу NP ====
В качестве сертификата выберем набор литералов <tex>\{y_1, ...,y_n\}</tex>, представляющий собой набор из нулей и единиц. Верификатору останется подставить эти значения в качестве аргументов в формулу <tex>\phi(x_1, ..., x_n)</tex> и проверить, выдает ли она единицу. Длина сертификата и время работы верификатора, очевидно, удовлетворяют условиям полиномиальности.
==== Доказательство принадлежности классу NPH ====
