Класс NP

В теории сложности Класс NP - класс языков (задач), ответ на которые можно проверить за полиномиальное время Для того, чтобы формализовать определение класса NP введем несколько определений.

NTIME

Классом NTIME(f) по аналогии с DTIME называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и время ее работы не превосходит [math]f(n)\,\![/math], где [math]n\,\![/math] [math]-\,\![/math] длина входа.

[math]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\,\![/math].

NSPACE

Классом NSPACE(f) по аналогии с DSPACE называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше [math]f(n)\,\![/math], где [math]n\,\![/math] [math]-\,\![/math] длина входа.

[math]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\,\![/math].

Класс [math]\Sigma_1[/math]

Классом [math]\Sigma_1[/math] называется класс языков(задач) L, таких что для каждого из них существует полиномиальный верификатор сертификата(утверждения) R, а также полином p, такие что слово l принадлежит языку L тогда и только тогда, когда существует сертификат(утверждение) y, длина которого не превосходит заданного полинома p, и сертификат удовлетворяет верификатору.

[math]\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\}[/math]

Теорема о равенстве [math]\Sigma_1 и NP[/math]

Формулировка

[math]\Sigma_1 = NP[/math]

Доказательство

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

[math]\Sigma_1 \in NP[/math]

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

m(x) {

 y := guess();
 return R(x,y);

}

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

[math]NP \in \Sigma_1[/math]

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

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

Примеры задач класса NP

• Задача о нахождении независимого множества заданного размера в графе. IND
• Задача о нахождении клики заданного размера в графе. CLICKUE
• Задача о нахождении вершинного покрытия заданного размера в графе. COVER
• Задача о удовлетворении булевой формулы, заданной в КНФ. SAT