202
правки
Изменения
Нет описания правки
== Определение Определения, связь Σ₁ и NP ==
{{Определение
|id=def1|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in \mathit{poly}}\!\!\mathrmoperatorname{NTIME}(p(n))</tex>.
}}
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых [[Недетерминированные вычисления|недетерминированной программой ]] за полиномиальное время.
{{Определение
|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|\le leqslant p(|x|), R(x,y)=1\}</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=
<tex>\mathrm{\Sigma_1}=\mathrm{NP}</tex>.
|proof=
}}
'''Примечание:''' определение <tex>\mathrm{\Sigma_1}</tex> часто называют также «определением <tex>\mathrm{NP }</tex> на языке сертификатов», а <tex>\Pi_1</tex>, соответственно, «определением <tex>\mathrm{coNP}</tex> на языке сертификатов».
== Свойства ==
|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>за полиномиальное время: <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>за полиномиальное время: <tex>r(x):\colon</tex> '''return ''' <tex>p(x) </tex>||'''or''' </tex> q(x) </tex>:3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>за полиномиальное время: <tex>r(x): n ← \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>за полиномиальное время: <tex>r(x):\colon</tex> n ← <tex>n = |x|</tex>x <tex>|prev = 1</tex> prev ← 1 '''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<br/tex>итераций, т.к. на каждой итерации левая граница диапазона увеличивается как минимум на 1.
}}
== Примеры языков из NP ==
== Связь 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 «решение» 3SAT за полиномиальное время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-полнота]]