Изменения

В теории сложности '''КлассNP''' <tex>NP</tex> - &mdash; класс языков (задач), ответ на которые можно проверить за полиномиальное время.

Определение Формальное определение класса '''NP ''' через класс '''[[Класс NTIME]].<tex>NP=\bigcup_{i=0}^{\infty} NTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} NTIME(in^k)</tex>''' выглядит так:

'''NP'''=<tex>\bigcup_{i==NTIME===Классом 0}^{\infty}</tex> '''NTIME(f) по аналогии с [[Класс DTIME|DTIME]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и время ее работы не превосходит '''<tex>f(nin^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty}</tex>, где '''NTIME'''<tex>n(in^k)</tex> - длина входа.

===Класс <tex>NTIME(f(n)) = \{ L | \exists НМТ m : L(m)=L, T(m,x) \le f(|x|) \}Sigma_1</tex>. ===NSPACE===Классом NSPACE(f) по аналогии с [[Класс DSPACE|DSPACE]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и память, используемая ею Альтернативным определением класса '''NP''' является определение на любом входе, не больше <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входаязыке сертификатов.

Будем говорить, что <tex>y</tex> является сертификатом принадлежности <tex>x</tex> языку <tex>NSPACE(f(n)) = \{ L \mid \exists НМТ m : L</tex>, если существует полиномиальное отношение (mверификатор)=L<tex>R</tex>, \delta такое что <tex>R(mx,xy) \le f(|=1</tex> тогда и только тогда, когда <tex>x|) \}</tex> принадлежит <tex>L</tex>.

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

<tex>\Sigma_1 = NP</tex>= '''NP'''

Построим доказательство равенство равенства из доказательств двух взаимных включений.

<tex>\Sigma_1 \subset NP</tex>&sub; '''NP'''

Построим программу, работающую за полином (из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в '''NP'''.

'''NP''' &sub; <tex>NP \subset \Sigma_1</tex>

Пусть <tex> L \in NP </tex>&isin; '''NP''' . Тогда существует НМТ <tex>m</tex>, распознающая <tex>L</tex>. Построим сертификат <tex>y </tex> как последовательность недетерминированных выборов машины <tex>m</tex>, приводящих к допуску слова. Верификатором сертификата <tex>R </tex> выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.

Теорема доказана.

* [[NP-полнота задачи BH1N|Задача о нахождении независимого множества заданного размера в графеBH1N]]. IND* Задача о нахождении клики заданного размера в графе[[NP-полнота задач о вершинном покрытии, клике и независимом множестве|вершинном покрытии, клике и независимом множестве]]. CLIQUE* Задача о нахождении вершинного покрытия заданного размера [[NP-полнота задачи о выполнимости булевой формулы в графе. COVER* Задача о форме КНФ|удовлетворении булевой формулы, заданной в КНФ]]. SAT [[Category:NP]]