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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры языков из coNP: переоформил примеры, доказал первый)
(Свойства: оформил псевдокод в техе)
Строка 43: Строка 43:
 
Пусть <tex>p</tex> разрешает <tex>L_1</tex>, а <tex>q</tex> разрешает <tex>L_2</tex>.
 
Пусть <tex>p</tex> разрешает <tex>L_1</tex>, а <tex>q</tex> разрешает <tex>L_2</tex>.
  
1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
+
* Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
  r(x):
+
  <tex>r(x)\colon</tex>
   '''return''' p(x) '''and''' q(x)
+
   '''return''' <tex>p(x)</tex> '''and''' <tex>q(x)</tex>
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
+
* Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
  r(x):
+
  <tex>r(x)\colon</tex>
   '''return''' p(x) '''or''' q(x)  
+
   '''return''' <tex>p(x)</tex> '''or''' <tex>q(x)</tex>
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
+
* Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
  r(x):
+
  <tex>r(x)\colon</tex>
   n = <tex>|</tex>x<tex>|</tex>
+
   <tex>n = |x|</tex>
   mid =<sup>?</sup> {1 .. n}
+
   <tex>mid \gets?\ \{1 \mathinner{\ldotp\ldotp} n\}</tex>
   '''return''' p(x[1 .. mid]) '''and''' q(x[mid+1 .. n])
+
   '''return''' <tex>p(x[1 \mathinner{\ldotp\ldotp} mid])</tex> '''and''' <tex>q(x[mid+1 \mathinner{\ldotp\ldotp} n])</tex>
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
+
* Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
 
<code>
 
<code>
  r(x):
+
  <tex>r(x)\colon</tex>
   n = <tex>|</tex>x<tex>|</tex>
+
   <tex>n = |x|</tex>
  prev = 1
+
  <tex>prev = 1</tex>
 
   '''do'''
 
   '''do'''
     cur =<sup>?</sup> {prev .. n}
+
     <tex>cur \gets?\  \{prev \mathinner{\ldotp\ldotp} n\}</tex>
     '''if not''' p(x[prev .. cur])
+
     '''if not''' <tex>p(x[prev \mathinner{\ldotp\ldotp} cur])</tex>
 
       '''return''' ''false''
 
       '''return''' ''false''
     prev = cur + 1
+
     <tex>prev = cur + 1</tex>
   '''while''' cur != n
+
   '''while''' <tex>cur \ne n</tex>
 
   '''return''' ''true''
 
   '''return''' ''true''
 
</code>
 
</code>

Версия 21:11, 24 марта 2016

Определения, связь Σ₁ и NP

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

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

Определение:
[math]\mathrm{coNP} = \{L \bigm| \overline{L} \in \mathrm{NP}\}[/math].

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

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

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

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

[math]\to \quad(\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]\gets \quad(\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] часто называют также «определением [math]\mathrm{NP}[/math] на языке сертификатов», а [math]\Pi_1[/math], соответственно, «определением [math]\mathrm{coNP}[/math] на языке сертификатов».

Свойства

Теорема:
Пусть [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].

  • Построим программу [math]r[/math], разрешающую [math]L_1\cap L_2[/math]:
[math]r(x)\colon[/math]
  return [math]p(x)[/math] and [math]q(x)[/math]
  • Построим программу [math]r[/math], разрешающую [math]L_1\cup L_2[/math]:
[math]r(x)\colon[/math]
  return [math]p(x)[/math] or [math]q(x)[/math]
  • Построим программу [math]r[/math], разрешающую [math]L_1L_2[/math]:
[math]r(x)\colon[/math]
  [math]n = |x|[/math]
  [math]mid \gets?\ \{1 \mathinner{\ldotp\ldotp} n\}[/math]
  return [math]p(x[1 \mathinner{\ldotp\ldotp} mid])[/math] and [math]q(x[mid+1 \mathinner{\ldotp\ldotp} n])[/math]
  • Построим программу [math]r[/math], разрешающую [math]L_1^*[/math]:

[math]r(x)\colon[/math]
  [math]n = |x|[/math]
  [math]prev = 1[/math]
  do
    [math]cur \gets?\  \{prev \mathinner{\ldotp\ldotp} n\}[/math]
    if not [math]p(x[prev \mathinner{\ldotp\ldotp} cur])[/math]
      return false
    [math]prev = cur + 1[/math]
  while [math]cur \ne n[/math]
  return true


[math]\triangleleft[/math]

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

Проблема раскраски вершин графа в [math]k[/math] цветов

Разрешается следующей недетерминированной программой за полиномиальное относительно числа вершин время:

[math]r(G)\colon[/math]
  n = [math]|V(G)|[/math]
  c [math]\gets? \{ 1, \dotsc, k \} ^ n[/math]
  for [math]uv[/math] in [math]E(G)[/math]
    if c[u] == c[v]
      return false
  return true

Проблема нахождения гамильтонова цикла

[math]r(G)\colon[/math]
  n = [math]|V(G)|[/math]
  p [math]\gets? V(G) ^ n[/math]
  for i = 1 to n
    if v[i] not in p
      return false
  p[n + 1] = p[1]
  for i = 1 to n
    if [math]p[i]p[i + 1] \notin E(G)[/math]
      return false
  return true

Задача о клике

[math]r(G)\colon[/math]
  n = [math]|V(G)|[/math]
  c [math]\gets? \{ 0, 1 \} ^ n[/math]
  for [math]u[/math] in [math]V(G)[/math]
    for [math]v[/math] in [math]V(G)[/math]
      if [math]u \ne v[/math] and [math]c[u][/math] and [math]c[v][/math] and [math]uv \notin E(G)[/math]
        return false
  return true

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

Примеры языков из coNP

Дополнение к задаче о сумме подмножеств

Языком этой задачи являются такие множества целых чисел, что сумма любого их непустого подмножества ненулевая. Этот язык является дополнением языка таких кортежей целых чисел, что какое-то их непустое подмножество имеет сумму ноль, разрешаемого за полиномиальное время следующей программой:

[math]r(S)\colon[/math]
  [math]Z \gets? \{ 0, 1 \}^{|S|}[/math]
  if [math]Z = 0^{|S|}[/math] or [math]\sum_{i=0}^{|S|} S[i] \cdot Z[i] \ne 0[/math]
    return false
  else
    return true
  

TAUT

Требуется определить, является ли заданная булева формула тавтологией. К этой задаче тривиально сводится дополнение к [math]\mathrm{SAT}[/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]-полной. При этом различие между задачами кажется совершенно незначительным.

См. также