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