Классы NP, coNP, Σ₁, Π₁

Материал из Викиконспекты
Версия от 12:56, 22 марта 2016; Iloskutov (обсуждение | вклад) (Переименовал co-NP в coNP)
Перейти к: навигация, поиск

Определение

Определение:
[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] — это множество языков, дополнение к которым лежит в NP.

Определение:
[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{\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) and q(x)

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

r(x):
  return p(x) or 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]) and 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 not p(x[prev .. cur])
      return false
    prev = cur + 1
  while cur != n
  return true


[math]\triangleleft[/math]

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

  • Проблема раскраски вершин графа в [math]k[/math] цветов.
    Разрешается следующей недетерминированной программой за полиномиальное время:
r(G):
  n = [math]|V(G)|[/math]
  c =? [math]\{ 1, \dotsc, k \} ^ n[/math]
  for uv in [math]E(G)[/math]
    if c[u] == c[v]
      return false
  return true
  • Проблема нахождения гамильтонова цикла:
 r(G):
   n = [math]|V(G)|[/math]
   p =? [math]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 p[i]p[i + 1] not in [math]E(G)[/math]
       return false
   return true

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

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

  • Даны [math]n[/math] целых чисел. Верно ли, что любое их непустое подмножество имеет ненулевую сумму?
  • TAUT: определить, является ли заданная булева формула тавтологией. К этой задаче тривиально сводится дополнение к SAT: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.

Связь 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]-полной. При этом различие между задачами кажется совершенно незначительным.

См. также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Классы_NP,_coNP,_Σ₁,_Π₁&oldid=52773»