1632
правки
Изменения
м
'''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''
Все эти языки Два последних языка также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]], если <tex>\mathrm{P \ne NP}</tex>, то существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
Требуется определить{{main|Теорема Бермана — Форчуна}}Язык булевых формул, является ли заданная булева формула тавтологиейявляющихся тавтологиями. К этой задаче этому языку тривиально сводится дополнение к <tex>\mathrm{SAT}</tex>: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.
rollbackEdits.php mass rollback
== Определения, связь Σ₁ и NP ==
{{Определение
|id=def1|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in \mathit{poly}}\!\!\operatorname{NTIME}(p(n))</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 \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>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
{{Определение
|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>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)\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>
<tex>n = |x|</tex>
== Примеры языков из NP ==
=== Язык палиндромов ===
Этот язык разрешается автоматом с магазинной памятью, то есть принадлежит <tex>\mathrm P</tex>, а следовательно, и <tex>\mathrm{NP}</tex>.
=== Язык задачи о раскраске вершин графа в <tex>k</tex> цветов ===
{{main|Раскраска графа}}
=== Язык гамильтоновых графов ===
{{main|Гамильтоновы графыNP-полнота задач о гамильтоновом цикле и пути в графах}}Рассмотрим следующий язык: <tex>\mathrm{HAM} = \{ G \mid G</tex> содержит гамильтонов цикл<tex>\}</tex>. Он разрешается следующей программой, работающей за полиномиальное относительно числа вершин время:
<tex>r(G)\colon</tex>
<tex>n = |V(G)|</tex>
'''if''' <tex>p[i]p[i + 1] \notin E(G)</tex>
'''return''' ''false''
'''return''' ''true''
== Примеры языков из coNP ==
=== Дополнение к задаче о сумме подмножеств Язык графов, не являющихся гамильтоновыми ===Языком этой задачи являются такие множества целых чисел, что сумма любого их непустого подмножества ненулевая. Этот язык является дополнением языка таких кортежей целых чисел, что какое-то их непустое подмножество имеет сумму ноль, разрешаемого за полиномиальное время следующей программой: принадлежит <tex>r(S)\colon</tex> <tex>Z \gets? \{ 0, 1 \}^mathrm{|S|coNP}</tex> '''if''' <tex>Z = 0^{|S|}</tex> '''or''' , так как является дополнением к языку гамильтоновых графов, принадлежащему <tex>\sum_{i=0}^mathrm{|S|NP} S[i] \cdot Z[i] \ne 0</tex> '''return''' ''false'' '''else''' '''return''' ''true'', как показано выше.
=== TAUT ===
== Связь 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>, при этом различие между задачами кажется совершенно незначительным:
!Принадлежит <tex>\mathrm P</tex>||<tex>\mathrm{NP}</tex>-полная
|-
|[[Обход_в_ширину|Поиск самых коротких простых путей]]||Поиск самых длинных простых путей<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 выполнимость]]
|}
* [[Недетерминированные вычисления]]
== Примечания ==<references/> [[Категория: Теория Классы сложности]][[Категория: Раскраски графовДетерминированные и недетерминированные вычисления, сложность по времени и по памяти ]][[Категория: Классы P и NP, NP-полнота]]
