Редактирование: Классы NP, coNP, Σ₁, Π₁

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
== Определения, связь Σ₁ и NP ==
+
== Определение ==
 
{{Определение
 
{{Определение
|id=def1
+
|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in poly}\!\!\operatorname{NTIME}(p(n))</tex>.
|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in \mathit{poly}}\!\!\operatorname{NTIME}(p(n))</tex>.
 
 
}}
 
}}
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых [[Недетерминированные вычисления|недетерминированной программой]] за полиномиальное время.
+
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
 
{{Определение
 
{{Определение
|definition=<tex>\mathrm{coNP} = \{L \bigm| \overline{L} \in \mathrm{NP}\}</tex>.
+
|definition=<tex>\textrm{co-NP} = \{L \bigm| \overline{L} \in \mathrm{NP}\}</tex>.
 
}}
 
}}
То есть <tex>\mathrm{coNP}</tex> — это множество языков, дополнение к которым лежит в <tex>\mathrm{NP}</tex>.
+
То есть <tex>\textrm{co-NP}</tex> — это множество языков, дополнение к которым лежит в NP.
 
{{Определение
 
{{Определение
|definition=<tex>\mathrm{\Sigma_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) \in \mathit{poly} : x\in L\Leftrightarrow\exists y : |y|\leqslant p(|x|), R(x,y)=1\}</tex>.
+
|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>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
 
Нестрого говоря, <tex>\mathrm{\Sigma_1}</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
{{Определение
+
 
|definition=<tex>\mathrm{\Pi_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) \in \mathit{poly} : x\in L\Leftrightarrow\forall y : |y|\leqslant p(|x|), R(x,y)=1\}</tex>.
 
}}
 
То есть <tex>\Pi_1</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) нельзя предъявить сертификат длины, ограниченной неким полиномом, опровергающий принадлежность слова языку и проверяемый верификатором. Легко видеть, что <tex>\Pi_1</tex> — множество языков, дополнения к которым лежат в <tex>\Sigma_1</tex>.
 
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
 
<tex>\mathrm{\Sigma_1}=\mathrm{NP}</tex>.
 
<tex>\mathrm{\Sigma_1}=\mathrm{NP}</tex>.
 
|proof=
 
|proof=
<tex>\Rightarrow \quad(\mathrm{\Sigma_1} \subset \mathrm{NP})</tex>.
+
*<tex>\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>.
: Пусть <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):
  <tex>q(x)\colon</tex>
+
   y = <tex>\{0,1\}^{p(|x|)}</tex>
   <tex>y = \{0,1\}^{p(|x|)}</tex>
+
   '''return''' R(x,y)
   '''return''' <tex>R(x,y)</tex>
+
Если <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>\Leftarrow \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>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> часто называют также «определением <tex>\mathrm{NP}</tex> на языке сертификатов», а <tex>\Pi_1</tex>, соответственно, «определением <tex>\mathrm{coNP}</tex> на языке сертификатов».
+
'''Примечание:''' определение <tex>\mathrm{\Sigma_1}</tex> часто называют также «определением NP на языке сертификатов».
  
 
== Свойства ==
 
== Свойства ==
Строка 37: Строка 32:
 
|statement=
 
|statement=
 
Пусть <tex>L_1,L_2\in \mathrm{NP}</tex>. Тогда:
 
Пусть <tex>L_1,L_2\in \mathrm{NP}</tex>. Тогда:
#<tex>L_1\cap 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_1\cup L_2\in \mathrm{NP}</tex>;
#<tex>L_1L_2\in \mathrm{NP}</tex>.
+
#<tex>L_1L_2\in \mathrm{NP}</tex>;
 
#<tex>L_1^*\in \mathrm{NP}</tex>.
 
#<tex>L_1^*\in \mathrm{NP}</tex>.
 
|proof=
 
|proof=
 
Пусть <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> за полиномиальное время:
+
1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
  <tex>r(x)\colon</tex>
+
  r(x):
   '''return''' <tex>p(x)</tex> '''and''' <tex>q(x)</tex>
+
   '''return''' p(x) '''and''' q(x)
:2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex> за полиномиальное время:
+
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
  <tex>r(x)\colon</tex>
+
  r(x):
   '''return''' <tex>p(x)</tex> '''or''' <tex>q(x)</tex>
+
   '''return''' p(x) '''or''' q(x)  
:3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex> за полиномиальное время:
+
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
  <tex>r(x)\colon</tex>
+
  r(x):
  <tex>n = |x|</tex>
+
  n = <tex>|</tex>x<tex>|</tex>
   <tex>mid \gets?\ \{1 \mathinner{\ldotp\ldotp} n\}</tex>
+
   mid =<sup>?</sup> {1 .. n}
   '''return''' <tex>p(x[1 \mathinner{\ldotp\ldotp} mid])</tex> '''and''' <tex>q(x[mid+1 \mathinner{\ldotp\ldotp} n])</tex>
+
   '''return''' p(x[1 .. mid]) '''and''' q(x[mid+1 .. n])
:4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex> за полиномиальное время:
+
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
<tex>r(x)\colon</tex>
+
<code>
  <tex>n = |x|</tex>
+
r(x):
   <tex>prev = 1</tex>
+
  n = <tex>|</tex>x<tex>|</tex>
 +
   prev = 1
 
   '''do'''
 
   '''do'''
     <tex>cur \gets?\  \{prev \mathinner{\ldotp\ldotp} n\}</tex>
+
     cur =<sup>?</sup> {prev .. n}
     '''if not''' <tex>p(x[prev \mathinner{\ldotp\ldotp} cur])</tex>
+
     '''if not''' p(x[prev .. cur])
 
       '''return''' ''false''
 
       '''return''' ''false''
     <tex>prev = cur + 1</tex>
+
     prev = cur + 1
   '''while''' <tex>cur \ne n</tex>
+
   '''while''' cur != n
 
   '''return''' ''true''
 
   '''return''' ''true''
: Цикл совершит не более <tex>n</tex> итераций, т.к. на каждой итерации левая граница диапазона увеличивается как минимум на 1.
+
</code>
 +
<br>
 
}}
 
}}
  
 
== Примеры языков из NP ==
 
== Примеры языков из NP ==
=== Язык палиндромов ===
+
* Проблема раскраски вершин графа в <tex>k</tex> цветов.<br><!--
Этот язык разрешается автоматом с магазинной памятью, то есть принадлежит <tex>\mathrm P</tex>, а следовательно, и <tex>\mathrm{NP}</tex>.
+
-->Разрешается следующей недетерминированной программой за полиномиальное время:
=== Язык задачи о раскраске вершин графа в <tex>k</tex> цветов ===
+
  r(G):
{{main|Раскраска графа}}
+
   n = <tex>|V(G)|</tex>
Переформулируем задачу в терминах принадлежности языку: пусть <tex> L = \{ \langle G, k \rangle \mid </tex>&nbsp; вершины <tex>G</tex> можно раскрасить в <tex>k</tex> цветов <tex>\}</tex>.
+
   c =<sup>?</sup> <tex>\{ 1, \dotsc, k \} ^ n</tex>
 
+
   '''for''' uv '''in''' <tex>E(G)</tex>
Этот язык разрешается следующей недетерминированной программой за полиномиальное относительно числа вершин и рёбер время:
+
     '''if''' c[u] == c[v]
  <tex>r(\langle G, k \rangle)\colon</tex>
 
   <tex>n = |V(G)|</tex>
 
   <tex>c \gets?\ \{ 1, \dotsc, k \} ^ n</tex>
 
   '''for''' <tex>uv</tex> '''in''' <tex>E(G)</tex>
 
     '''if''' <tex>c[u]</tex> == <tex>c[v]</tex>
 
 
       '''return''' ''false''
 
       '''return''' ''false''
 
   '''return''' ''true''
 
   '''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>-полным.
  
=== Язык гамильтоновых графов ===
+
== Примеры языков из co-NP ==
{{main|NP-полнота задач о гамильтоновом цикле и пути в графах}}
+
* Даны <tex>n</tex> целых чисел. Верно ли, что любое их непустое подмножество имеет ненулевую сумму?
Рассмотрим следующий язык: <tex>\mathrm{HAM} = \{ G \mid G</tex> содержит гамильтонов цикл<tex>\}</tex>. Он разрешается следующей программой, работающей за полиномиальное относительно числа вершин время:
+
* TAUT: определить, является ли заданная булева формула тавтологией. К этой задаче тривиально сводится дополнение к SAT: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.
<tex>r(G)\colon</tex>
 
  <tex>n = |V(G)|</tex>
 
  <tex>p \gets?\ V(G) ^ n</tex>
 
  '''for''' <tex>v</tex> '''in''' <tex>V(G)</tex>
 
    '''if''' <tex>v \notin p</tex>
 
      '''return''' ''false''
 
  <tex>p[n + 1] = p[1]</tex>
 
  '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
 
    '''if''' <tex>p[i]p[i + 1] \notin E(G)</tex>
 
      '''return''' ''false''
 
  '''return''' ''true''
 
 
 
Два последних языка также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]], если <tex>\mathrm{P \ne NP}</tex>, то существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
 
 
 
== Примеры языков из coNP ==
 
=== Язык графов, не являющихся гамильтоновыми ===
 
Этот язык принадлежит <tex>\mathrm{coNP}</tex>, так как является дополнением к языку гамильтоновых графов, принадлежащему <tex>\mathrm{NP}</tex>, как показано выше.
 
 
 
=== TAUT ===
 
{{main|Теорема Бермана — Форчуна}}
 
Язык булевых формул, являющихся тавтологиями. К этому языку тривиально сводится дополнение к <tex>\mathrm{SAT}</tex>: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.
 
  
 
== Связь P и NP ==
 
== Связь P и NP ==
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]].
+
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]]; различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>:
Кроме того, были предприняты различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>:
+
*[http://arxiv.org/abs/1011.3944 «решение» 3SAT за полиномиальное время];
* «решение» 3SAT за полиномиальное время<ref>[http://arxiv.org/abs/1011.3944 Non-Orthodox Combinatorial Models Based on Discordant Structures]</ref>
+
*[http://www.cse.yorku.ca/~aaw/Zambito/TSP_Survey.pdf задача о коммивояжере].
* задача о коммивояжёре<ref>[http://www.cse.yorku.ca/~aaw/Zambito/TSP_Survey.pdf The Traveling Salesman Problem: A Comprehensive Survey]</ref>.
 
  
Некоторые задачи из <tex>\mathrm{P}</tex> очень похожи на задачи из <tex>\mathrm{NP}</tex>, при этом различие между задачами кажется совершенно незначительным:
+
Некоторые задачи из <tex>\mathrm{P}</tex> очень похожи на задачи из <tex>\mathrm{NP}</tex>. В каждой из приведенных ниже пар задач первая разрешима за полиномиальное время, а вторая является <tex>\mathrm{NP}</tex>-полной. При этом различие между задачами кажется совершенно незначительным.
{| class="wikitable"
+
*Поиск [[Обход_в_ширину|самых коротких]] и самых длинных простых путей;
|-
+
*[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров]] и [[Гамильтоновы_графы|гамильтонов]] циклы;
!Принадлежит <tex>\mathrm P</tex>||<tex>\mathrm{NP}</tex>-полная
+
*2-CNF и 3-CNF выполнимость.
|-
 
|[[Обход_в_ширину|Поиск самых коротких простых путей]]||Поиск самых длинных простых путей<ref>[//en.wikipedia.org/wiki/Longest_path_problem Longest path problem - Wikipedia]</ref>
 
|-
 
|[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл]]||[[NP-полнота задач о гамильтоновом цикле и пути в графах|Гамильтонов цикл]]
 
|-
 
|[[2SAT|2-CNF выполнимость]]||[[Примеры NP-полных языков#NP-полнота 3-SAT|3-CNF выполнимость]]
 
|}
 
  
 
== См. также ==
 
== См. также ==
 
* [[Недетерминированные вычисления]]
 
* [[Недетерминированные вычисления]]
  
== Примечания ==
+
[[Категория: Теория сложности]]
<references/>
 
 
 
[[Категория: Классы сложности]]
 
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ]]
 
[[Категория: Классы P и NP, NP-полнота]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: