165
правок
Изменения
Нет описания правки
В теории сложности '''КлассNP''' <tex>NP</tex> — класс языков (задач), ответ на которые можно проверить за полиномиальное время.
===Определение===
'''NP'''=<tex>NP=\bigcup_{i=0}^{\infty} </tex> '''NTIME'''<tex>(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} </tex> '''NTIME'''<tex>(in^k)</tex>
===Класс <tex>\Sigma_1</tex>===
Альтернативным определением класса <tex>'''NP</tex> ''' является определение на языке сертификатов.
Будем говорить, что <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> NP</tex>==
===Формулировка===
<tex>\Sigma_1 = NP</tex>= '''NP'''
===Доказательство===
Построим доказательство равенство из доказательств двух взаимных включений.
<tex>\Sigma_1 \subset NP</tex>⊂ '''NP'''
Построим программу, работающую за полином (из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в <tex>'''NP</tex>'''.
Вхождение доказано.
'''NP''' ⊂ <tex>NP \subset \Sigma_1</tex>
Пусть <tex> L \in NP </tex>∈ '''NP''' . Тогда существует НМТ <tex>m</tex>, распознающая <tex>L</tex>. Построим сертификат <tex>y </tex> как последовательность недетерминированных выборов машины <tex>m</tex>, приводящих к допуску слова. Верификатором сертификата <tex>R </tex> выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.
Теорема доказана.
