Классы NP, coNP, Σ₁, Π₁ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 16: Строка 16:
 
Пусть <tex>L \in \mathrm{\Sigma_1}</tex>. Тогда существуют <tex>R(x,y)</tex> и полином <tex>p</tex> из определения <tex>\mathrm{\Sigma_1}</tex>. Построим недетерминированную программу <tex>q(x)</tex>, разрешающую <tex>L</tex>.
 
Пусть <tex>L \in \mathrm{\Sigma_1}</tex>. Тогда существуют <tex>R(x,y)</tex> и полином <tex>p</tex> из определения <tex>\mathrm{\Sigma_1}</tex>. Построим недетерминированную программу <tex>q(x)</tex>, разрешающую <tex>L</tex>.
 
   q(x):
 
   q(x):
     y <tex>\leftarrow?\{0,1\}^{\le p(|x|)}</tex>
+
     y &larr; <tex>\{0,1\}^{p(|x|)}</tex>
     return <tex>R(x,y)</tex>
+
     return R(x,y)
 
Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.
 
Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.
 
*<tex>\mathrm{NP} \subset \mathrm{\Sigma_1}</tex>.
 
*<tex>\mathrm{NP} \subset \mathrm{\Sigma_1}</tex>.
Строка 37: Строка 37:
 
1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
 
1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
 
   r(x):
 
   r(x):
   return p(x) <tex>\&\&</tex> q(x)  
+
   return p(x) && q(x)  
 
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
 
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
 
   r(x):
 
   r(x):
Строка 43: Строка 43:
 
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
 
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
 
   r(x):
 
   r(x):
     n <tex>\leftarrow|x|</tex>
+
     n &larr; <tex>|</tex>x<tex>|</tex>
    mid <tex>\leftarrow?</tex> {1..n}
+
    mid &larr;? {1..n}
     return p(x[1..mid]) <tex>\&\&</tex> q(x[mid+1..n])
+
     return p(x[1..mid]) && q(x[mid+1..n])
 
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
 
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
 
   r(x):
 
   r(x):
     n <tex>\leftarrow|x|</tex>
+
     n &larr; <tex>|</tex>x<tex>|</tex>
    prev <tex>\leftarrow</tex> 1
+
    prev &larr; 1
 
     do
 
     do
       cur <tex>\leftarrow?</tex> {prev..n}
+
       cur &larr;? {prev..n}
 
       if (!p(x[prev..cur]))
 
       if (!p(x[prev..cur]))
 
         return false
 
         return false
       prev <tex>\leftarrow</tex> cur+1
+
       prev &larr; cur+1
 
     while (cur != n)
 
     while (cur != n)
 
     return true
 
     return true
Строка 64: Строка 64:
 
* Задача о клике;
 
* Задача о клике;
 
* [http://arxiv.org/abs/cs.CC/0210020 Тетрис]
 
* [http://arxiv.org/abs/cs.CC/0210020 Тетрис]
Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. О существовании <tex>\mathrm{NP}</tex> языка, не являющегося <tex>\mathrm{NP}</tex>-полным гласит [[Теорема Ладнера|теорема Ладнера]].
+
Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]] существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
  
 
== Связь P и NP ==
 
== Связь P и NP ==

Версия 11:54, 9 июня 2012

Определение

Определение:
[math]\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))[/math].

То есть [math]\mathrm{NP}[/math] — это множество языков, разрешимых недетерминированной программой за полиномиальное время.

Определение:
[math]\mathrm{\Sigma_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) - poly:x\in L\Leftrightarrow\exists y : |y|\le p(|x|), R(x,y)=1\}[/math].

Нестрого говоря, [math]\mathrm{\Sigma_1}[/math] — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор [math]R(x,y)[/math], а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.

Теорема:
[math]\mathrm{\Sigma_1}=\mathrm{NP}[/math].
Доказательство:
[math]\triangleright[/math]
  • [math]\mathrm{\Sigma_1} \subset \mathrm{NP}[/math].

Пусть [math]L \in \mathrm{\Sigma_1}[/math]. Тогда существуют [math]R(x,y)[/math] и полином [math]p[/math] из определения [math]\mathrm{\Sigma_1}[/math]. Построим недетерминированную программу [math]q(x)[/math], разрешающую [math]L[/math].

 q(x):
   y ← [math]\{0,1\}^{p(|x|)}[/math]
   return R(x,y)

Если [math]x\in L[/math], то программа сможет «угадать» подходящий сертификат. Если [math]x\notin L[/math], то подходящего сертификата не существует по определению. Таким образом, [math]q[/math] разрешает [math]L[/math], следовательно [math]L\in \mathrm{NP}[/math].

  • [math]\mathrm{NP} \subset \mathrm{\Sigma_1}[/math].
Пусть [math]L\in \mathrm{NP}[/math]. Тогда существует недетерминированная программа [math]q(x)[/math], разрешающая этот язык. Построим верификатор [math]R(x,y)[/math]. В качестве сертификата будем использовать последовательность выборов в программе [math]q[/math], приводящую к допуску слова (такой сертификат имеет полиномиальную длину, поскольку выборов в [math]q[/math] может быть сделано не более, чем время ее работы, то есть не более, чем полином). Верификатор будет аналогичен программе [math]q[/math], только вместо каждого недетерминированного выбора он будет присваивать значение, указанное в сертификате. Если [math]x\in L[/math], то в [math]q[/math] существует последовательность выборов таких, что [math]q(x)=1[/math], следовательно существует и верный сертификат. Если [math]x\notin L[/math], то для любой последовательности выборов [math]q(x)=0[/math], следовательно подходящего сертификата не существует. Таким образом, [math]L \in \mathrm{\Sigma_1}[/math].
[math]\triangleleft[/math]

Примечание: определение [math]\mathrm{\Sigma_1}[/math] часто называют также «определением NP на языке сертификатов».

Свойства

Теорема:
Пусть [math]L_1,L_2\in \mathrm{NP}[/math]. Тогда:
  1. [math]L_1\cap L_2\in \mathrm{NP}[/math];
  2. [math]L_1\cup L_2\in \mathrm{NP}[/math];
  3. [math]L_1L_2\in \mathrm{NP}[/math];
  4. [math]L_1^*\in \mathrm{NP}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]p[/math] разрешает [math]L_1[/math], а [math]q[/math] разрешает [math]L_2[/math].

1. Построим программу [math]r[/math], разрешающую [math]L_1\cap L_2[/math]:

 r(x):
  return p(x) && q(x) 

2. Построим программу [math]r[/math], разрешающую [math]L_1\cup L_2[/math]:

 r(x):
  return p(x) [math]||[/math] q(x) 

3. Построим программу [math]r[/math], разрешающую [math]L_1L_2[/math]:

 r(x):
   n ← [math]|[/math]x[math]|[/math]
   mid ←? {1..n}
   return p(x[1..mid]) && q(x[mid+1..n])

4. Построим программу [math]r[/math], разрешающую [math]L_1^*[/math]:

 r(x):
   n ← [math]|[/math]x[math]|[/math]
   prev ← 1
   do
     cur ←? {prev..n}
     if (!p(x[prev..cur]))
       return false
     prev ← cur+1
   while (cur != n)
   return true

[math]\triangleleft[/math]

Примеры NP-языков

  • Язык раскрасок графа в [math]k[/math] цветов;
  • Задача о клике;
  • Тетрис

Все эти языки также являются [math]\mathrm{NP}[/math]-полными. По теореме Ладнера существует язык из [math]\mathrm{NP}[/math], не являющийся [math]\mathrm{NP}[/math]-полным.

Связь P и NP

Очевидно, что [math]\mathrm{P} \subseteq \mathrm{NP}[/math], так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти редкий [math]\mathrm{NP}[/math]-полный язык; было доказано, что доказательство должно быть нерелятивизующимся; различные попытки найти полиномиальные решения для задач из [math]\mathrm{NPC}[/math]:

Некоторые задачи из [math]\mathrm{P}[/math] очень похожи на задачи из [math]\mathrm{NP}[/math]. В каждой из приведенных ниже пар задач первая разрешима за полиномиальное время, а вторая является [math]\mathrm{NP}[/math]-полной. При этом различие между задачами кажется совершенно незначительным.

См. также