Изменения

Альтернативным определением класса <tex>NP </tex> является определение на языке сертификатов.

Будем говорить, что <tex>y </tex> является сертификатом принадлежности <tex>x </tex> языку <tex>L</tex>, если существует полиномиальное отношение (верификатор) <tex>R</tex>, такое что <tex>R(x,y)=1</tex> тогда и только тогда, когда</tex>x</tex> принадлежит <tex>L</tex>.

Классом <tex>\Sigma_1</tex> называется класс языков (задач) <tex>L</tex>, таких что для каждого из них существует полиномиальный верификатор сертификата <tex>R</tex>, а также полином <tex>p</tex>, такие что слово <tex>l </tex> принадлежит языку <tex>L </tex> тогда и только тогда, когда существует сертификат (утверждение) <tex>y</tex>, длина которого не превосходит заданного полинома <tex>p</tex>, и сертификат <tex>y</tex> удовлетворяет верификатору<tex>R</tex>.