130
правок
Изменения
Добавил определение co-NP, доказал первый пример, поправил псевдокод
== Определение ==
{{Определение
|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in poly}\mathrm!\!\operatorname{NTIME}(p(n))</tex>.
}}
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
{{Определение
|definition=<tex>\textrm{co-NP} = \{L \bigm| \overline{L} \in \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 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} \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>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>.
1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
'''return''' p(x) '''and''' q(x)
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
'''return''' p(x) '''or''' q(x)
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
<code>
</code>
<br>
== Примеры языков из NP ==
* Язык раскрасок Проблема раскраски вершин графа в <tex>k</tex> цветов.<br><!---->Разрешается следующей программой: r(G): n = <tex>|V(G)|</tex> c =<sup>?</sup> <tex>\{ 1, \dotsc, k \} ^ n</tex> '''for''' uv '''in''' <tex>E(G)</tex> '''if''' c[u] == c[v] '''return''' ''false'' '''return''' ''true''
* Задача о клике.
* [http://arxiv.org/abs/cs.CC/0210020 Тетрис].
Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]] существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
== Примеры языков из co-NP ==
* Даны <tex>n</tex> целых чисел. Верно ли, что любое их непустое подмножество имеет ненулевую сумму?
== Связь P и NP ==
