83
правки
Изменения
м
<code>mПостроим программу, работающую за полином (xиз свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее){ y := guess(); return R(x,y);}которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </codetex>в NP.
Нет описания правки
В теории сложности '''Класс NP''' <tex>NP</tex> - класс языков (задач), ответ на которые можно проверить за полиномиальное времяДля того, чтобы формализовать определение ===Определение===Определение класса NP введем несколько определенийчерез [[Класс NTIME]].<tex>NP=\bigcup_{i=0}^{\infty} NTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} NTIME(in^k)</tex>
===NTIME===
Классом NTIME(f) по аналогии с [[Класс DTIME|DTIME]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и время ее работы не превосходит <mathtex>f(n)\,\!</mathtex>, где <mathtex>n\,\!</math> <mathtex>-\,\!</math> длина входа.
<mathtex>NTIME(f(n)) = \{ L \mid | \exists </math> НМТ <math>m : L(m)=L, T(m,x) \le f(|x|) \}</math>, где <math>|x|\,\!</math> <math>-\,\!</math> длина <math>x\,\!</mathtex>.
===NSPACE===
Классом NSPACE(f) по аналогии с [[Класс DSPACE|DSPACE]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входа.
<mathtex>NSPACE(f(n)) = \{ L \mid \exists </math> НМТ <math>m : L(m)=L, \delta (m,x) \le f(|x|) \}</math>, где <math>|x|\,\!</math> <math>-\,\!</math> длина <math>x\,\!</mathtex>.
===Класс <tex>\Sigma_1</tex>===
Классом <tex>\Sigma_1</tex> называется класс языков(задач) L, таких что для каждого из них существует полиномиальный верификатор сертификата(утверждения) R, а также полином p, такие что слово l принадлежит языку L тогда и только тогда, когда существует сертификат(утверждение) y, длина которого не превосходит заданного полинома p, и сертификат удовлетворяет верификатору.
<tex>\Sigma_1 = \{L|\exists R(x,y) \in Poly, p \in Poly | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex>
Построим доказательство равенство из доказательств двух взаимных включений.
<mathtex>\Sigma_1 \subset NP</math> Построим программу, работающую за полином(из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в NP.
Вхождение доказано.
<mathtex>NP \subset \Sigma_1</mathtex>
Пусть <tex> L \in NP </tex>. Тогда существует НМТ m, распознающая L. Построим сертификат y как последовательность недетерминированных выборов машины m, приводящих к допуску слова. Верификатором сертификата R выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.
==Примеры задач класса NP==
* Задача о нахождении независимого множества заданного размера в графе. IND
* Задача о нахождении клики заданного размера в графе. CLICKUECLIQUE
* Задача о нахождении вершинного покрытия заданного размера в графе. COVER
* Задача о удовлетворении булевой формулы, заданной в КНФ. SAT
