1
правка
Изменения
м
Исправлена опечатка в формуле: l переименована в x
Будем говорить, что <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>lx</tex> принадлежит языку <tex>L</tex> тогда и только тогда, когда существует сертификат <tex>y</tex>, длина которого не превосходит заданного полинома <tex>p</tex>, и сертификат <tex>y</tex> удовлетворяет верификатору <tex>R</tex>.
<tex>\Sigma_1 = \{L|\exists R(x,y) \in P, p \in Poly | l x \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex>
==Теорема о равенстве <tex>\Sigma_1 </tex> и <tex> NP</tex>==
