Классы NP, coNP, Σ₁, Π₁ — различия между версиями
(Новая страница: «{{Определение |definition=<tex>\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))</tex>. }} То есть <tex>\mathrm{NP}</tex> — это...») |
м (rollbackEdits.php mass rollback) |
||
(не показаны 63 промежуточные версии 10 участников) | |||
Строка 1: | Строка 1: | ||
+ | == Определения, связь Σ₁ и NP == | ||
{{Определение | {{Определение | ||
− | |definition=<tex>\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\ | + | |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> — это множество языков, разрешимых [[Недетерминированные вычисления|недетерминированной программой]] за полиномиальное время. |
{{Определение | {{Определение | ||
− | |definition=<tex>\mathrm{\Sigma_1}=\{L|\exists R(x,y)\in \mathrm{P}, p(n) | + | |definition=<tex>\mathrm{coNP} = \{L \bigm| \overline{L} \in \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 \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 \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>L \in \mathrm{\Sigma_1}</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>q(x)\colon</tex> | |
− | + | <tex>y = \{0,1\}^{p(|x|)}</tex> | |
− | Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>. | + | '''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>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>\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>\mathrm{\Sigma_1}</tex> часто называют также | + | '''Примечание:''' определение <tex>\mathrm{\Sigma_1}</tex> часто называют также «определением <tex>\mathrm{NP}</tex> на языке сертификатов», а <tex>\Pi_1</tex>, соответственно, «определением <tex>\mathrm{coNP}</tex> на языке сертификатов». |
− | + | == Свойства == | |
{{Теорема | {{Теорема | ||
|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> | |
− | + | '''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> | |
− | + | '''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>n = |x|</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> | |
− | 4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>: | + | :4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex> за полиномиальное время: |
− | + | <tex>r(x)\colon</tex> | |
− | + | <tex>n = |x|</tex> | |
− | + | <tex>prev = 1</tex> | |
− | + | '''do''' | |
− | + | <tex>cur \gets?\ \{prev \mathinner{\ldotp\ldotp} n\}</tex> | |
− | + | '''if not''' <tex>p(x[prev \mathinner{\ldotp\ldotp} cur])</tex> | |
− | + | '''return''' ''false'' | |
− | + | <tex>prev = cur + 1</tex> | |
− | + | '''while''' <tex>cur \ne n</tex> | |
− | + | '''return''' ''true'' | |
− | + | : Цикл совершит не более <tex>n</tex> итераций, т.к. на каждой итерации левая граница диапазона увеличивается как минимум на 1. | |
}} | }} | ||
− | + | == Примеры языков из NP == | |
− | + | === Язык палиндромов === | |
− | + | Этот язык разрешается автоматом с магазинной памятью, то есть принадлежит <tex>\mathrm P</tex>, а следовательно, и <tex>\mathrm{NP}</tex>. | |
− | + | === Язык задачи о раскраске вершин графа в <tex>k</tex> цветов === | |
− | + | {{main|Раскраска графа}} | |
− | + | Переформулируем задачу в терминах принадлежности языку: пусть <tex> L = \{ \langle G, k \rangle \mid </tex> вершины <tex>G</tex> можно раскрасить в <tex>k</tex> цветов <tex>\}</tex>. | |
+ | |||
+ | Этот язык разрешается следующей недетерминированной программой за полиномиальное относительно числа вершин и рёбер время: | ||
+ | <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''' ''true'' | ||
+ | |||
+ | === Язык гамильтоновых графов === | ||
+ | {{main|NP-полнота задач о гамильтоновом цикле и пути в графах}} | ||
+ | Рассмотрим следующий язык: <tex>\mathrm{HAM} = \{ G \mid G</tex> содержит гамильтонов цикл<tex>\}</tex>. Он разрешается следующей программой, работающей за полиномиальное относительно числа вершин время: | ||
+ | <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 == | ||
+ | Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]]. | ||
+ | Кроме того, были предприняты различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>: | ||
+ | * «решение» 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>, при этом различие между задачами кажется совершенно незначительным: | ||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | !Принадлежит <tex>\mathrm P</tex>||<tex>\mathrm{NP}</tex>-полная | ||
+ | |- | ||
+ | |[[Обход_в_ширину|Поиск самых коротких простых путей]]||Поиск самых длинных простых путей<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-полнота]] |
Текущая версия на 19:17, 4 сентября 2022
Содержание
Определения, связь Σ₁ и NP
Определение: |
. |
То есть недетерминированной программой за полиномиальное время.
— это множество языков, разрешимыхОпределение: |
. |
То есть
— это множество языков, дополнение к которым лежит в .Определение: |
. |
Нестрого говоря,
— это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор , а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.Определение: |
. |
То есть
— это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор , а для каждого слова из языка (и только для слова из языка) нельзя предъявить сертификат длины, ограниченной неким полиномом, опровергающий принадлежность слова языку и проверяемый верификатором. Легко видеть, что — множество языков, дополнения к которым лежат в .Теорема: |
. |
Доказательство: |
.
return
.
|
Примечание: определение
часто называют также «определением на языке сертификатов», а , соответственно, «определением на языке сертификатов».Свойства
Теорема: |
Пусть . Тогда:
|
Доказательство: |
Пусть разрешает , а разрешает .
return and
return or
return and
do if not return false while return true
|
Примеры языков из NP
Язык палиндромов
Этот язык разрешается автоматом с магазинной памятью, то есть принадлежит
, а следовательно, и .Язык задачи о раскраске вершин графа в цветов
Переформулируем задачу в терминах принадлежности языку: пусть
вершины можно раскрасить в цветов .Этот язык разрешается следующей недетерминированной программой за полиномиальное относительно числа вершин и рёбер время:
for in if == return false return true
Язык гамильтоновых графов
Рассмотрим следующий язык:
содержит гамильтонов цикл . Он разрешается следующей программой, работающей за полиномиальное относительно числа вершин время:for in if return false for to if return false return true
Два последних языка также являются . По -полнымитеореме Ладнера, если , то существует язык из , не являющийся -полным.
Примеры языков из coNP
Язык графов, не являющихся гамильтоновыми
Этот язык принадлежит
, так как является дополнением к языку гамильтоновых графов, принадлежащему , как показано выше.TAUT
Язык булевых формул, являющихся тавтологиями. К этому языку тривиально сводится дополнение к
: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.Связь P и NP
Очевидно, что редкий ; было доказано, что -полный языкдоказательство должно быть нерелятивизующимся. Кроме того, были предприняты различные попытки найти полиномиальные решения для задач из :
, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найтиНекоторые задачи из
очень похожи на задачи из , при этом различие между задачами кажется совершенно незначительным:Принадлежит | -полная |
---|---|
Поиск самых коротких простых путей | Поиск самых длинных простых путей[3] |
Эйлеров цикл | Гамильтонов цикл |
2-CNF выполнимость | 3-CNF выполнимость |