83
правки
Изменения
м
Нет описания правки
В теории сложности '''Класс''' <tex>NP</tex> - класс языков (задач), ответ на которые можно проверить за полиномиальное время.
===Определение===
===Класс <tex>\Sigma_1</tex>===
Классом <tex>\Sigma_1</tex> называется класс языков (задач) L, таких что для каждого из них существует полиномиальный верификатор сертификата(утверждения) R, а также полином p, такие что слово l принадлежит языку L тогда и только тогда, когда существует сертификат(утверждение) y, длина которого не превосходит заданного полинома p, и сертификат удовлетворяет верификатору.
<tex>\Sigma_1 = \{L|\exists R(x,y) \in PolyP, p \in Poly | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex>
==Теорема о равенстве <tex>\Sigma_1 </tex> и <tex> NP</tex>==
<tex>\Sigma_1 \subset NP</tex>
Построим программу, работающую за полином (из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в <tex>NP</tex>.
Вхождение доказано.
Пусть <tex> L \in NP </tex>. Тогда существует НМТ m, распознающая L. Построим сертификат y как последовательность недетерминированных выборов машины m, приводящих к допуску слова. Верификатором сертификата R выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.
Теорема доказана.
==Примеры задач класса NP==
