Изменения

Тут должен быть заголовок.== Определения, связь Σ₁ и NP =={{Определение|id=def1|definition= Определение =<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in \mathit{poly}}\!\!\operatorname{NTIME}(p(n))</tex>.}}То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых [[Недетерминированные вычисления|недетерминированной программой]] за полиномиальное время.

|definition=<tex>\mathrm{NPcoNP}=\bigcup{L \bigm| \limits_overline{p(n) L} \in poly}\mathrm{NTIMENP}\}(p(n))</tex>.

То есть <tex>\mathrm{NPcoNP}</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>\Rightarrow \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>. <tex>q(x):\colon</tex> <tex>y\leftarrow?= \{0,1\}^{\le p(|x|)}</tex> <tex> '''return</tex> ''' <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>\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{NP }</tex> на языке сертификатов», а <tex>\Pi_1</tex>, соответственно, «определением <tex>\mathrm{coNP}</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>;.

:1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>за полиномиальное время: <tex>r(x):\colon</tex> <tex> '''return</tex> ''' <tex>p(x)</tex> <tex>\&\&</tex> '''and''' <tex>q(x)</tex> :2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>за полиномиальное время: <tex>r(x):\colon</tex> <tex> '''return</tex> ''' <tex>p(x)</tex> <tex>||</tex> '''or''' <tex>q(x)</tex> :3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>за полиномиальное время: <tex>r(x):\colon</tex> <tex>n\leftarrow= |x|</tex> <tex>mid\leftarrowgets?\ \{1..\mathinner{\ldotp\ldotp} n\}</tex> <tex> '''return</tex> ''' <tex>p(x[1..\mathinner{\ldotp\ldotp} mid])</tex> <tex>\&\&</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> <tex>n\leftarrow= |x|</tex> <tex>prev\leftarrow = 1</tex> <tex> '''do</tex>''' <tex>cur\leftarrowgets?\ \{prev..\mathinner{\ldotp\ldotp} n\}</tex> <tex> '''ifnot''' </tex> <tex>(!p(x[prev..\mathinner{\ldotp\ldotp} cur]))</tex> <tex> '''return</tex> <tex>''' ''false</tex>'' <tex>prev\leftarrow = cur+1</tex> <tex> '''while</tex> ''' <tex>(cur</tex> <tex>!=</tex> <tex>\ne n)</tex> <tex> '''return''' ''true'': Цикл совершит не более </tex> <tex>truen</tex><br>итераций, т.к. на каждой итерации левая граница диапазона увеличивается как минимум на 1.

== Примеры языков из NP-языков ==* === Язык раскрасок палиндромов ===Этот язык разрешается автоматом с магазинной памятью, то есть принадлежит <tex>\mathrm P</tex>, а следовательно, и <tex>\mathrm{NP}</tex>.=== Язык задачи о раскраске вершин графа в <tex>k</tex> цветов==={{main|Раскраска графа}}Переформулируем задачу в терминах принадлежности языку: пусть <tex> L = \{ \langle G, k \rangle \mid </tex>&nbsp;вершины <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-полнота задач о клике;гамильтоновом цикле и пути в графах}}* [httpРассмотрим следующий язык:<tex>\mathrm{HAM} = \{ G \mid G</tex> содержит гамильтонов цикл<tex>\}</arxivtex>.orgОн разрешается следующей программой, работающей за полиномиальное относительно числа вершин время: <tex>r(G)\colon</abstex> <tex>n = |V(G)|</tex> <tex>p \gets?\ V(G) ^ n</tex> '''for''' <tex>v</cs.CCtex> '''in''' <tex>V(G)</tex> '''if''' <tex>v \notin p</0210020 Тетрис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>: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.

Очевидно, что <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-полнота]]