Изменения

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