Класс NP

2020-10-04T11:22:32Z

Yoprst: Исправлена опечатка в формуле: l переименована в x

В теории сложности '''Класс NP''' — класс языков (задач), ответ на которые можно проверить за полиномиальное время.

===Определение===
Формальное определение класса '''NP''' через класс '''[[NTIME]]''' выглядит так:

'''NP'''=<tex>\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>===
Альтернативным определением класса '''NP''' является определение на языке сертификатов.

Будем говорить, что <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>L</tex>, таких что для каждого из них существует полиномиальный верификатор <tex>R</tex>, а также полином <tex>p</tex>, такие что слово <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 P, p \in Poly | 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</tex> = '''NP'''
===Доказательство===
Построим доказательство равенства из доказательств двух взаимных включений.

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

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

Вхождение доказано.

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

Пусть <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]].
* Задача о [[NP-полнота задач о вершинном покрытии, клике и независимом множестве|вершинном покрытии, клике и независимом множестве]].
* Задача о [[NP-полнота задачи о выполнимости булевой формулы в форме КНФ|удовлетворении булевой формулы, заданной в КНФ]]. SAT

[[Category:NP]]

Викиконспекты - Вклад участника [ru]

Класс NP