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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Связь P и NP: Переоформил примеры похожих задач из P и NPC в табличку и добавил ссылки)
м (rollbackEdits.php mass rollback)
 
(не показано 18 промежуточных версий 6 участников)
Строка 1: Строка 1:
 
== Определения, связь Σ₁ и NP ==
 
== Определения, связь Σ₁ и NP ==
 
{{Определение
 
{{Определение
|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in poly}\!\!\operatorname{NTIME}(p(n))</tex>.
+
|id=def1
 +
|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in \mathit{poly}}\!\!\operatorname{NTIME}(p(n))</tex>.
 
}}
 
}}
 
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых [[Недетерминированные вычисления|недетерминированной программой]] за полиномиальное время.
 
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых [[Недетерминированные вычисления|недетерминированной программой]] за полиномиальное время.
Строка 9: Строка 10:
 
То есть <tex>\mathrm{coNP}</tex> — это множество языков, дополнение к которым лежит в <tex>\mathrm{NP}</tex>.
 
То есть <tex>\mathrm{coNP}</tex> — это множество языков, дополнение к которым лежит в <tex>\mathrm{NP}</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|\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 \mathit{poly} : x\in L\Leftrightarrow\exists y : |y|\leqslant 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 poly : x\in L\Leftrightarrow\forall y : |y|\leqslant p(|x|), R(x,y)=1\}</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>.
 
То есть <tex>\Pi_1</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) нельзя предъявить сертификат длины, ограниченной неким полиномом, опровергающий принадлежность слова языку и проверяемый верификатором. Легко видеть, что <tex>\Pi_1</tex> — множество языков, дополнения к которым лежат в <tex>\Sigma_1</tex>.
Строка 43: Строка 44:
 
Пусть <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>
 
  <tex>r(x)\colon</tex>
 
   '''return''' <tex>p(x)</tex> '''and''' <tex>q(x)</tex>
 
   '''return''' <tex>p(x)</tex> '''and''' <tex>q(x)</tex>
: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>
 
  <tex>r(x)\colon</tex>
 
   '''return''' <tex>p(x)</tex> '''or''' <tex>q(x)</tex>
 
   '''return''' <tex>p(x)</tex> '''or''' <tex>q(x)</tex>
:3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
+
:3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex> за полиномиальное время:
 
  <tex>r(x)\colon</tex>
 
  <tex>r(x)\colon</tex>
 
   <tex>n = |x|</tex>
 
   <tex>n = |x|</tex>
 
   <tex>mid \gets?\ \{1 \mathinner{\ldotp\ldotp} n\}</tex>
 
   <tex>mid \gets?\ \{1 \mathinner{\ldotp\ldotp} n\}</tex>
 
   '''return''' <tex>p(x[1 \mathinner{\ldotp\ldotp} mid])</tex> '''and''' <tex>q(x[mid+1 \mathinner{\ldotp\ldotp} n])</tex>
 
   '''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>:
+
:4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex> за полиномиальное время:
 
  <tex>r(x)\colon</tex>
 
  <tex>r(x)\colon</tex>
 
   <tex>n = |x|</tex>
 
   <tex>n = |x|</tex>
Строка 69: Строка 70:
  
 
== Примеры языков из NP ==
 
== Примеры языков из NP ==
 +
=== Язык палиндромов ===
 +
Этот язык разрешается автоматом с магазинной памятью, то есть принадлежит <tex>\mathrm P</tex>, а следовательно, и <tex>\mathrm{NP}</tex>.
 
=== Язык задачи о раскраске вершин графа в <tex>k</tex> цветов ===
 
=== Язык задачи о раскраске вершин графа в <tex>k</tex> цветов ===
 
{{main|Раскраска графа}}
 
{{main|Раскраска графа}}
Строка 83: Строка 86:
  
 
=== Язык гамильтоновых графов ===
 
=== Язык гамильтоновых графов ===
{{main|Гамильтоновы графы}}
+
{{main|NP-полнота задач о гамильтоновом цикле и пути в графах}}
 +
Рассмотрим следующий язык: <tex>\mathrm{HAM} = \{ G \mid G</tex> содержит гамильтонов цикл<tex>\}</tex>. Он разрешается следующей программой, работающей за полиномиальное относительно числа вершин время:
 
  <tex>r(G)\colon</tex>
 
  <tex>r(G)\colon</tex>
 
   <tex>n = |V(G)|</tex>
 
   <tex>n = |V(G)|</tex>
Строка 94: Строка 98:
 
     '''if''' <tex>p[i]p[i + 1] \notin E(G)</tex>
 
     '''if''' <tex>p[i]p[i + 1] \notin E(G)</tex>
 
       '''return''' ''false''
 
       '''return''' ''false''
  '''return''' ''true''
 
=== Задача о клике ===
 
<tex>r(G)\colon</tex>
 
  n = <tex>|V(G)|</tex>
 
  c <tex>\gets? \{ 0, 1 \} ^ n</tex>
 
  '''for''' <tex>u</tex> '''in''' <tex>V(G)</tex>
 
    '''for''' <tex>v</tex> '''in''' <tex>V(G)</tex>
 
      '''if''' <tex>u \ne v</tex> '''and''' <tex>c[u]</tex> '''and''' <tex>c[v]</tex> '''and''' <tex>uv \notin E(G)</tex>
 
        '''return''' ''false''
 
 
   '''return''' ''true''
 
   '''return''' ''true''
  
Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]], если <tex>\mathrm{P \ne NP}</tex>, то существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
+
Два последних языка также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]], если <tex>\mathrm{P \ne NP}</tex>, то существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
  
 
== Примеры языков из coNP ==
 
== Примеры языков из coNP ==
=== Дополнение к задаче о сумме подмножеств ===
+
=== Язык графов, не являющихся гамильтоновыми ===
Языком этой задачи являются такие множества целых чисел, что сумма любого их непустого подмножества ненулевая. Этот язык является дополнением языка таких кортежей целых чисел, что какое-то их непустое подмножество имеет сумму ноль, разрешаемого за полиномиальное время следующей программой:
+
Этот язык принадлежит <tex>\mathrm{coNP}</tex>, так как является дополнением к языку гамильтоновых графов, принадлежащему <tex>\mathrm{NP}</tex>, как показано выше.
<tex>r(S)\colon</tex>
 
  <tex>Z \gets? \{ 0, 1 \}^{|S|}</tex>
 
  '''if''' <tex>Z = 0^{|S|}</tex> '''or''' <tex>\sum_{i=0}^{|S|} S[i] \cdot Z[i] \ne 0</tex>
 
    '''return''' ''false''
 
  '''else'''
 
    '''return''' ''true''
 
 
    
 
    
 
=== TAUT ===
 
=== TAUT ===
Требуется определить, является ли заданная булева формула тавтологией. К этой задаче тривиально сводится дополнение к <tex>\mathrm{SAT}</tex>: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.
+
{{main|Теорема Бермана — Форчуна}}
 +
Язык булевых формул, являющихся тавтологиями. К этому языку тривиально сводится дополнение к <tex>\mathrm{SAT}</tex>: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.
  
 
== Связь P и NP ==
 
== Связь P и NP ==
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]]; различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>:
+
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]].
*[http://arxiv.org/abs/1011.3944 «решение» 3SAT за полиномиальное время];
+
Кроме того, были предприняты различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>:
*[http://www.cse.yorku.ca/~aaw/Zambito/TSP_Survey.pdf задача о коммивояжере].
+
* «решение» 3SAT за полиномиальное время<ref>[http://arxiv.org/abs/1011.3944 Non-Orthodox Combinatorial Models Based on Discordant Structures]</ref>
 +
* задача о коммивояжёре<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>, при этом различие между задачами кажется совершенно незначительным:
Строка 130: Строка 121:
 
!Принадлежит <tex>\mathrm P</tex>||<tex>\mathrm{NP}</tex>-полная
 
!Принадлежит <tex>\mathrm P</tex>||<tex>\mathrm{NP}</tex>-полная
 
|-
 
|-
|[[Обход_в_ширину|Поиск самых коротких простых путей]]||[//en.wikipedia.org/wiki/Longest_path_problem Поиск самых длинных простых путей]
+
|[[Обход_в_ширину|Поиск самых коротких простых путей]]||Поиск самых длинных простых путей<ref>[//en.wikipedia.org/wiki/Longest_path_problem Longest path problem - Wikipedia]</ref>
 
|-
 
|-
|[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл]]||[[Гамильтоновы_графы|Гамильтонов цикл]]
+
|[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл]]||[[NP-полнота задач о гамильтоновом цикле и пути в графах|Гамильтонов цикл]]
 
|-
 
|-
|[http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf 2-CNF выполнимость]||[[Примеры NP-полных языков#NP-полнота 3-SAT|3-CNF выполнимость]]
+
|[[2SAT|2-CNF выполнимость]]||[[Примеры NP-полных языков#NP-полнота 3-SAT|3-CNF выполнимость]]
 
|}
 
|}
  
Строка 140: Строка 131:
 
* [[Недетерминированные вычисления]]
 
* [[Недетерминированные вычисления]]
  
[[Категория: Теория сложности]]
+
== Примечания ==
[[Категория: Раскраски графов]]
+
<references/>
 +
 
 +
[[Категория: Классы сложности]]
 +
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ]]
 +
[[Категория: Классы P и NP, NP-полнота]]

Текущая версия на 19:17, 4 сентября 2022

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

Определение:
[math]\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in \mathit{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 \mathit{poly} : x\in L\Leftrightarrow\exists y : |y|\leqslant 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 \mathit{poly} : x\in L\Leftrightarrow\forall y : |y|\leqslant 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]\Rightarrow \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].
[math]q(x)\colon[/math]
  [math]y = \{0,1\}^{p(|x|)}[/math]
  return [math]R(x,y)[/math]
Если [math]x\in L[/math], то программа сможет «угадать» подходящий сертификат. Если [math]x\notin L[/math], то подходящего сертификата не существует по определению. Таким образом, [math]q[/math] разрешает [math]L[/math], следовательно [math]L\in \mathrm{NP}[/math].

[math]\Leftarrow \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].

1. Построим программу [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]
2. Построим программу [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]
3. Построим программу [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]
4. Построим программу [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]n[/math] итераций, т.к. на каждой итерации левая граница диапазона увеличивается как минимум на 1.
[math]\triangleleft[/math]

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

Язык палиндромов

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

Язык задачи о раскраске вершин графа в [math]k[/math] цветов

Основная статья: Раскраска графа

Переформулируем задачу в терминах принадлежности языку: пусть [math] L = \{ \langle G, k \rangle \mid [/math]  вершины [math]G[/math] можно раскрасить в [math]k[/math] цветов [math]\}[/math].

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

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

Язык гамильтоновых графов

Рассмотрим следующий язык: [math]\mathrm{HAM} = \{ G \mid G[/math] содержит гамильтонов цикл[math]\}[/math]. Он разрешается следующей программой, работающей за полиномиальное относительно числа вершин время:

[math]r(G)\colon[/math]
  [math]n = |V(G)|[/math]
  [math]p \gets?\ V(G) ^ n[/math]
  for [math]v[/math] in [math]V(G)[/math]
    if [math]v \notin p[/math]
      return false
  [math]p[n + 1] = p[1][/math]
  for [math]i = 1[/math] to [math]n[/math]
    if [math]p[i]p[i + 1] \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]\mathrm{coNP}[/math], так как является дополнением к языку гамильтоновых графов, принадлежащему [math]\mathrm{NP}[/math], как показано выше.

TAUT

Язык булевых формул, являющихся тавтологиями. К этому языку тривиально сводится дополнение к [math]\mathrm{SAT}[/math]: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.

Связь P и NP

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

  • «решение» 3SAT за полиномиальное время[1]
  • задача о коммивояжёре[2].

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

Принадлежит [math]\mathrm P[/math] [math]\mathrm{NP}[/math]-полная
Поиск самых коротких простых путей Поиск самых длинных простых путей[3]
Эйлеров цикл Гамильтонов цикл
2-CNF выполнимость 3-CNF выполнимость

См. также

Примечания