1632
правки
Изменения
м
rollbackEdits.php mass rollback
Будем говорить, что <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>==
* Задача о [[NP-полнота задач о вершинном покрытии, клике и независимом множестве|вершинном покрытии, клике и независимом множестве]].
* Задача о [[NP-полнота задачи о выполнимости булевой формулы в форме КНФ|удовлетворении булевой формулы, заданной в КНФ]]. SAT
[[Category:NP]]
