Просмотр исходного текста страницы Классы NP, coNP, Σ₁, Π₁

== Определение ==
{{Определение
|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in poly}\!\!\operatorname{NTIME}(p(n))</tex>.
}}
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
{{Определение
|definition=<tex>\mathrm{coNP} = \{L \bigm| \overline{L} \in \mathrm{NP}\}</tex>.
}}
То есть <tex>\mathrm{coNP}</tex> — это множество языков, дополнение к которым лежит в NP.
{{Определение
|definition=<tex>\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\}</tex>.
}}
Нестрого говоря, <tex>\mathrm{\Sigma_1}</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.

{{Теорема
|statement=
<tex>\mathrm{\Sigma_1}=\mathrm{NP}</tex>.
|proof=
<tex>\to \quad(\mathrm{\Sigma_1} \subset \mathrm{NP})</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):
:    y = <tex>\{0,1\}^{p(|x|)}</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>\gets \quad(\mathrm{NP} \subset \mathrm{\Sigma_1})</tex>.
:Пусть <tex>L\in \mathrm{NP}</tex>. Тогда существует недетерминированная программа <tex>q(x)</tex>, разрешающая этот язык. Построим верификатор <tex>R(x,y)</tex>. В качестве сертификата будем использовать последовательность выборов в программе <tex>q</tex>, приводящую к допуску слова (такой сертификат имеет полиномиальную длину, поскольку выборов в <tex>q</tex> может быть сделано не более, чем время ее работы, то есть не более, чем полином). Верификатор будет аналогичен программе <tex>q</tex>, только вместо каждого недетерминированного выбора он будет присваивать значение, указанное в сертификате. Если <tex>x\in L</tex>, то в <tex>q</tex> существует последовательность выборов таких, что <tex>q(x)=1</tex>, следовательно существует и верный сертификат. Если <tex>x\notin L</tex>, то для любой последовательности выборов <tex>q(x)=0</tex>, следовательно подходящего сертификата не существует. Таким образом, <tex>L \in \mathrm{\Sigma_1}</tex>.
}}
'''Примечание:''' определение <tex>\mathrm{\Sigma_1}</tex> часто называют также «определением NP на языке сертификатов».

== Свойства ==
{{Теорема
|statement=
Пусть <tex>L_1,L_2\in \mathrm{NP}</tex>. Тогда:
#<tex>L_1\cap L_2\in \mathrm{NP}</tex>;
#<tex>L_1\cup L_2\in \mathrm{NP}</tex>;
#<tex>L_1L_2\in \mathrm{NP}</tex>;
#<tex>L_1^*\in \mathrm{NP}</tex>.
|proof=
Пусть <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>:
 r(x):
   '''return''' p(x) '''and''' q(x)
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
 r(x):
   '''return''' p(x) '''or''' q(x) 
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
 r(x):
   n = <tex>|</tex>x<tex>|</tex>
   mid =<sup>?</sup> {1 .. n}
   '''return''' p(x[1 .. mid]) '''and''' q(x[mid+1 .. n])
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
<code>
 r(x):
   n = <tex>|</tex>x<tex>|</tex>
   prev = 1
   '''do'''
     cur =<sup>?</sup> {prev .. n}
     '''if not''' p(x[prev .. cur])
       '''return''' ''false''
     prev = cur + 1
   '''while''' cur != n
   '''return''' ''true''
</code>
<br>
}}

== Примеры языков из NP ==
* Проблема раскраски вершин графа в <tex>k</tex> цветов.<br><!--
-->Разрешается следующей недетерминированной программой за полиномиальное время:
 r(G):
   n = <tex>|V(G)|</tex>
   c =<sup>?</sup> <tex>\{ 1, \dotsc, k \} ^ n</tex>
   '''for''' uv '''in''' <tex>E(G)</tex>
     '''if''' c[u] == c[v]
       '''return''' ''false''
   '''return''' ''true''
* Проблема нахождения гамильтонова цикла:
  r(G):
    n = <tex>|V(G)|</tex>
    p =<sup>?</sup> <tex>V(G) ^ n</tex>
    '''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''' <tex>E(G)</tex>
        '''return''' ''false''
    '''return''' ''true''
* Задача о клике.
* [[NP-полнота игры Тетрис|Тетрис]].
Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]], существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.

== Примеры языков из coNP ==
* Даны <tex>n</tex> целых чисел. Верно ли, что любое их непустое подмножество имеет ненулевую сумму?
* TAUT: определить, является ли заданная булева формула тавтологией. К этой задаче тривиально сводится дополнение к SAT: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.

== Связь P и NP ==
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]]; различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>:
*[http://arxiv.org/abs/1011.3944 «решение» 3SAT за полиномиальное время];
*[http://www.cse.yorku.ca/~aaw/Zambito/TSP_Survey.pdf задача о коммивояжере].

Некоторые задачи из <tex>\mathrm{P}</tex> очень похожи на задачи из <tex>\mathrm{NP}</tex>. В каждой из приведенных ниже пар задач первая разрешима за полиномиальное время, а вторая является <tex>\mathrm{NP}</tex>-полной. При этом различие между задачами кажется совершенно незначительным.
*Поиск [[Обход_в_ширину|самых коротких]] и самых длинных простых путей;
*[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров]] и [[Гамильтоновы_графы|гамильтонов]] циклы;
*2-CNF и 3-CNF выполнимость.

== См. также ==
* [[Недетерминированные вычисления]]

[[Категория: Теория сложности]]