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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
В теории сложности '''Класс NP''' - класс языков (задач), ответ на которые можно проверить за полиномиальное время
+
В теории сложности '''Класс''' <tex>NP</tex> - класс языков (задач), ответ на которые можно проверить за полиномиальное время
Для того, чтобы формализовать определение класса NP введем несколько определений.
+
 
 +
===Определение===
 +
Определение класса NP через [[Класс NTIME]].
 +
<tex>NP=\bigcup_{i=0}^{\infty} NTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} NTIME(in^k)</tex>
  
 
===NTIME===
 
===NTIME===
Классом NTIME(f) по аналогии с [[Класс DTIME|DTIME]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и время ее работы не превосходит <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входа.
+
Классом NTIME(f) по аналогии с [[Класс DTIME|DTIME]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и время ее работы не превосходит <tex>f(n)</tex>, где <tex>n</tex> - длина входа.
  
<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>.
+
<tex>NTIME(f(n)) = \{ L | \exists НМТ m : L(m)=L, T(m,x) \le f(|x|) \}</tex>.
  
 
===NSPACE===
 
===NSPACE===
 
Классом NSPACE(f) по аналогии с [[Класс DSPACE|DSPACE]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входа.
 
Классом NSPACE(f) по аналогии с [[Класс DSPACE|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>.
+
<tex>NSPACE(f(n)) = \{ L \mid \exists НМТ m : L(m)=L, \delta (m,x) \le f(|x|) \}</tex>.
  
 
===Класс <tex>\Sigma_1</tex>===
 
===Класс <tex>\Sigma_1</tex>===
Классом <tex>\Sigma_1</tex> называется класс языков(задач) L, таких что для каждого из них существует полиномиальный верификатор сертификата(утверждения) R, а также полином p, такие что слово l принадлежит языку L тогда и только тогда, когда существует сертификат(утверждение) y, длина которого не превосходит заданного полинома p, и сертификат удовлетворяет верификатору.
+
Классом <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 Poly, p \in Poly | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex>
Строка 23: Строка 26:
 
Построим доказательство равенство из доказательств двух взаимных включений.
 
Построим доказательство равенство из доказательств двух взаимных включений.
  
<math>\Sigma_1 \subset NP</math>
+
<tex>\Sigma_1 \subset NP</tex>
 
 
Построим программу, работающую за полином(из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в NP.
 
  
<code>
+
Построим программу, работающую за полином (из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в NP.
m(x)
 
{
 
  y := guess();
 
  return R(x,y);
 
}
 
</code>
 
  
 
Вхождение доказано.
 
Вхождение доказано.
  
<math>NP \subset \Sigma_1</math>
+
<tex>NP \subset \Sigma_1</tex>
  
 
Пусть <tex> L \in NP </tex>. Тогда существует НМТ m, распознающая L. Построим сертификат y как последовательность недетерминированных выборов машины m, приводящих к допуску слова. Верификатором сертификата R выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.
 
Пусть <tex> L \in NP </tex>. Тогда существует НМТ m, распознающая L. Построим сертификат y как последовательность недетерминированных выборов машины m, приводящих к допуску слова. Верификатором сертификата R выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.
Строка 45: Строка 40:
 
==Примеры задач класса NP==
 
==Примеры задач класса NP==
 
* Задача о нахождении независимого множества заданного размера в графе. IND
 
* Задача о нахождении независимого множества заданного размера в графе. IND
* Задача о нахождении клики заданного размера в графе. CLICKUE
+
* Задача о нахождении клики заданного размера в графе. CLIQUE
 
* Задача о нахождении вершинного покрытия заданного размера в графе. COVER
 
* Задача о нахождении вершинного покрытия заданного размера в графе. COVER
 
* Задача о удовлетворении булевой формулы, заданной в КНФ. SAT
 
* Задача о удовлетворении булевой формулы, заданной в КНФ. SAT

Версия 17:12, 18 марта 2010

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

Определение

Определение класса NP через Класс NTIME. [math]NP=\bigcup_{i=0}^{\infty} NTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} NTIME(in^k)[/math]

NTIME

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

[math]NTIME(f(n)) = \{ L | \exists НМТ m : L(m)=L, T(m,x) \le f(|x|) \}[/math].

NSPACE

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

[math]NSPACE(f(n)) = \{ L \mid \exists НМТ m : L(m)=L, \delta (m,x) \le f(|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 [/math] и [math] NP[/math]

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

[math]\Sigma_1 = NP[/math]

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

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

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

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

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

[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

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