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