Класс NP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(основные сведения)
 
м (Исправлена опечатка в формуле: l переименована в x)
(не показано 27 промежуточных версий 5 участников)
Строка 1: Строка 1:
В теории сложности '''Класс NP''' класс языков (задач), ответ на которые можно проверить за полиномиальное время
+
В теории сложности '''Класс NP''' — класс языков (задач), ответ на которые можно проверить за полиномиальное время.
Для того, чтобы формализовать определение класса NP введем несколько определений.
 
  
===NTIME===
+
===Определение===
Классом NTIME(f) по аналогии с [[Класс DTIME|DTIME]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и время ее работы не превосходит <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входа.
+
Формальное определение класса '''NP''' через класс '''[[NTIME]]''' выглядит так:
  
<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>.
+
'''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>
  
===NSPACE===
+
===Класс <tex>\Sigma_1</tex>===
Классом NSPACE(f) по аналогии с [[Класс DSPACE|DSPACE]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входа.
+
Альтернативным определением класса '''NP''' является определение на языке сертификатов.
  
<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>.
+
Будем говорить, что <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>\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</tex> называется класс языков(задач) L, таких что для каждого из них существует полиномиальный верификатор сертификата(утверждения) R, а также полином p, такие что слово l принадлежит языку L тогда и только тогда, когда существует сертификат(утверждение) y, длина которого не превосходит заданного полинома p, и сертификат удовлетворяет верификатору.
 
  
<tex>\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\}</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 и NP</tex>==
+
==Теорема о равенстве <tex>\Sigma_1 </tex> и <tex> NP</tex>==
 
===Формулировка===
 
===Формулировка===
<tex>\Sigma_1 = NP</tex>
+
<tex>\Sigma_1</tex> = '''NP'''
 
===Доказательство===
 
===Доказательство===
Построим доказательство равенство из доказательств двух взаимных включений.
+
Построим доказательство равенства из доказательств двух взаимных включений.
  
===<tex>\Sigma_1 \in NP</tex>===
+
<tex>\Sigma_1</tex> &sub; '''NP'''
Построим программу, работающую за полином(из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в NP.
 
  
m(x)
+
Построим программу, работающую за полином (из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1</tex> в '''NP'''.
{
 
  y := guess();
 
  return R(x,y);
 
}
 
  
 
Вхождение доказано.
 
Вхождение доказано.
  
===<tex>NP \in \Sigma_1</tex>===
+
'''NP''' &sub; <tex>\Sigma_1</tex>
Пусть <tex> L \in NP </tex>. Тогда существует НМТ m, распознающая L. Построим сертификат y как последовательность недетерминированных выборов машины m, приводящих к допуску слова. Верификатором сертификата R выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.
+
 
 +
Пусть <tex>L</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==
 
==Примеры задач класса NP==
* Задача о нахождении независимого множества заданного размера в графе. IND
+
* [[NP-полнота задачи BH1N|Задача BH1N]].
* Задача о нахождении клики заданного размера в графе. CLICKUE
+
* Задача о [[NP-полнота задач о вершинном покрытии, клике и независимом множестве|вершинном покрытии, клике и независимом множестве]].
* Задача о нахождении вершинного покрытия заданного размера в графе. COVER
+
* Задача о [[NP-полнота задачи о выполнимости булевой формулы в форме КНФ|удовлетворении булевой формулы, заданной в КНФ]]. SAT
* Задача о удовлетворении булевой формулы, заданной в КНФ. SAT
+
 
 +
[[Category:NP]]

Версия 14:22, 4 октября 2020

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

Определение

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

NP=[math]\bigcup_{i=0}^{\infty}[/math] NTIME[math](in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty}[/math] NTIME[math](in^k)[/math]

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

Альтернативным определением класса NP является определение на языке сертификатов.

Будем говорить, что [math]y[/math] является сертификатом принадлежности [math]x[/math] языку [math]L[/math], если существует полиномиальное отношение (верификатор) [math]R[/math], такое что [math]R(x,y)=1[/math] тогда и только тогда, когда [math]x[/math] принадлежит [math]L[/math].

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

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

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

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

[math]\Sigma_1[/math] = NP

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

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

[math]\Sigma_1[/math]NP

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

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

NP[math]\Sigma_1[/math]

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

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

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