Изменения

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