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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Класс \Sigma_1)
Строка 9: Строка 9:
 
Альтернативным определением класса <tex>NP</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>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>l</tex> принадлежит языку <tex>L</tex> тогда и только тогда, когда существует сертификат <tex>y</tex>, длина которого не превосходит заданного полинома <tex>p</tex>, и сертификат <tex>y</tex> удовлетворяет верификатору <tex>R</tex>.
 
Классом <tex>\Sigma_1</tex> называется класс языков (задач) <tex>L</tex>, таких что для каждого из них существует полиномиальный верификатор <tex>R</tex>, а также полином <tex>p</tex>, такие что слово <tex>l</tex> принадлежит языку <tex>L</tex> тогда и только тогда, когда существует сертификат <tex>y</tex>, длина которого не превосходит заданного полинома <tex>p</tex>, и сертификат <tex>y</tex> удовлетворяет верификатору <tex>R</tex>.

Версия 16:16, 29 мая 2010

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

Определение

Определение класса NP через класс NTIME и класс NSPACE.

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

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

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

Будем говорить, что [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]l[/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 | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}[/math]

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

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

[math]\Sigma_1 = NP[/math]

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

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

[math]\Sigma_1 \subset NP[/math]

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

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

[math]NP \subset \Sigma_1[/math]

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

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

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