Изменения

<tex> \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \bigm| m </tex> {{---}} недерминированная недетерминированная машина Тьюринга, <tex> m(x) = 1, T(m,x) \le t \rbrace </tex>

# <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex> <br> Нужно доказать, что <tex> \forall \mathrm{L} \in \mathrm{NP} </tex> существует полиномиальное [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведение по Карпу]] к языку <tex> \mathrm{BH_{1N}} </tex>. Рассмотрим произвольный язык <tex> \mathrm{L} \in \mathrm{NP} </tex>. Для него существует машина Тьюринга <tex> m </tex> и полином <tex> p(x) </tex>, такие что <tex> T(m, x) \le p(|x|), \mathrm{L}(m) = \mathrm{L} </tex>. Докажем, что <tex> \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} </tex>. Рассмотрим функцию <tex> f(x) = \langle m, x, 1^{p(|x|)} \rangle </tex>, по входным данным возвращающую тройку из описанной выше машины Тьюринга, входных данных и времени <tex> p(|x|)</tex> в унарной системе счисления. <br> <br> Проверим, что <tex> x \in \mathrm{L} \Leftrightarrow f(x) \in \mathrm{BH_{1N}} </tex>. <br> Пусть <tex> x \in L </tex>. Тогда <tex> m(x) = 1 </tex> за время не более <tex> p(|x|) </tex>, а значит <tex>\langle m,x, 1^{p(|x|)} \rangle = f(x) \in \mathrm{BH_{1N}} </tex>. <br> Пусть <tex>x \not\in L</tex>. Тогда <tex>m(x) = 0</tex> и <tex>\langle m,x, 1^{p(|x|)} \rangle = f(x) \notin \mathrm{BH_{1N}} </tex>. <br> <br> Это значит, что <tex> \forall \mathrm{L} \in \mathrm{NP}\ \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} </tex>, и из этого следует, что <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex>. <br><br># <tex> \mathrm{BH_{1N}} \in \mathrm{NP} </tex><br>Можно написать недетерминированную программу, которая будет по <tex> \langle m, x, 1^t \rangle </tex> моделировать <tex> t </tex> шагов <tex> m </tex> на входе <tex> x </tex>, выбирая недетерминированно соответствующие недетерминированные переходы, и если машина за это время допустила слово, то только тогда <tex> \langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} </tex>.

<tex> \mathrm{SAT} = \lbrace \varphi\ \bigm|\ mid \exists x : \varphi(x) = 1 \rbrace </tex>

# <tex> \mathrm{SAT}\in \mathrm{NPH} </tex># <tex> \mathrm{SAT}\in \mathrm{NP} </tex> <br>Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{SAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.# <tex> \mathrm{SAT}\in \mathrm{NPH} </tex> <br> Теперь докажем, что <tex> \mathrm{SAT}\in \mathrm{NPH} </tex>. Для этого сведём задачу <tex> \mathrm{BH_{1N}} </tex>, которая <tex> \mathrm{NP} </tex>-полна, к <tex> \mathrm{SAT} </tex>. Тогда получится, что любой язык из <tex> \mathrm{NP} </tex> может быть [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведен по Карпу]] к <tex> \mathrm{BH_{1N}} </tex>, и, по транзитивности сведения по Карпу, к <tex> \mathrm{SAT} </tex>. <br> По определению языка <tex> \mathrm{BH_{1N}} </tex>, у нас есть:#* недетерминированная машина Тьюринга <tex>m</tex>, причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы#* входное слово <tex>x</tex>#* время <tex>t</tex>, заданное в унарной системе счисления. #:Нам же надо построить такую булеву формулу <tex>\varphi</tex>, что она выполнима тогда, и только тогда, когда <tex>m</tex>, получив на вход <tex>x</tex>, делает не более <tex>t</tex> шагов и допускает это слово. <br> В любой момент времени мгновенное описание (МО) <tex>m</tex> есть строка <tex>z\#_qyb</tex>, где <tex>b</tex> &mdash; строка, состоящая из такого количества пробелов, чтобы длина всего МО была <tex>t + 1.</tex> Соответственно, начальное МО задаётся так: <tex>\#_sxb</tex>. Если же <tex>|x| > t</tex>, то будем считать, что на ленту записаны лишь первые <tex>t</tex> символов, ведь <tex>m</tex> не может обработать большее количество символов за <tex>t</tex> шагов. <br> Также нам удобно считать, что все вычисления проходят ровно за <tex>t + 1</tex> шагов, даже если мы попали в допускающее состояние раньше. То есть, мы разрешим переход <tex>q \vdash q</tex>, если в МО <tex>q</tex> есть допускающее состояние, так что, чтобы проверить, допустила ли машина слово, надо лишь проверить наличие допускающего состояния в МО <tex>q_t</tex>. <br> Тогда процесс работы машины <tex>m</tex> на входе <tex>x</tex>, то есть цепочка переходов <tex>q_0 \vdash q_1 \vdash \ldots \vdash q_t</tex> может быть представлен следующей таблицей : <table align="right" border="1" style="text-align:center" cellspacing="0"><tr> <td colspan=10>'''Процесс работы машины <tex>m</tex> на входе <tex>x</tex>''' </td></tr><tr> <td width="50"> MO </td> <td width="50" > 0 </td> <td width="50"> 1 </td> <td width="30">... </td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="30">... </td> <td width="50">t </td></tr><tr> <td width="50"> <tex>q_0</tex></td> <td width="50" > <tex>q_{0, 0}</tex></td> <td width="50"> <tex>q_{0, 1}</tex></td> <td width="30"></td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="30"></td> <td width="50"><tex>q_{0, t}</tex></td></tr><tr> <td width="50"> <tex>q_1</tex></td> <td width="50" > <tex>q_{1, 0}</tex></td> <td width="50"> <tex>q_{1, 1}</tex></td> <td width="30"></td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="30"></td> <td width="50"><tex>q_{1, t}</tex></td></tr><tr> <td width="50"> ...</td> <td width="50" > </td> <td width="50"> </td> <td width="30"></td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="30"></td> <td width="50"></td></tr><tr> <td width="50"> <tex> q_i </tex><font size /td> <td width= "50" > </td> <td width="50"> </td> <td width="30"></td><td width="50"> <tex> q_{i, j - 1} </tex></td><td width="50"> <tex> q_{i, j} </tex></td><td width="50"> <tex> q_{i, j + 1} </tex></td><td width="50"><tex> q_{i, j + 2} </tex> </td><td width="30"></td> <td width="50"></td></tr><tr> <td width="50"> <tex> q_{i+1} </tex></td> <td width="50" > </td> <td width="50"> </td> <td width="30"></td><td width="50"> <tex> q_{i+1, j - 1} </tex></td><td width="50"> <tex> q_{i+1, j} </tex></td><td width="50"> <tex> q_{i+1, j + 1} </tex></td><td width="50"></td><td width="30"></td> <td width="50"></td></tr><tr> <td width="50"> ...</td> <td width="50" > </td> <td width="50"> </td> <td width="30"></td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="30"></td> <td width="50"></td></tr><tr> <td width="50"> <tex>q_t</tex></td> <td width="50" > <tex>q_{t, 0}</tex></td> <td width="50"> <tex>q_{t, 1}</tex></td> <td width="30"></td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="50"> </td><td width="30"></td> <td width="50"><tex>q_{t, t}</tex></td></tr></table> ::Каждый элемент таблицы <tex>q_{i, j}\in \Sigma \cup Q</tex>. И для каждого такого элемента заведём <tex>|\Sigma| + |Q|</tex> переменных <tex>Y_{i, j, c} = [q_{i, j} = c]\ \forall c \in \Sigma \cup Q</tex> <br> Общий вид формулы: <tex>p(\varphi)= S \land T \land N \land C</tex>. for ::# <tex>S</tex> отвечает за правильный старт, то есть символ <tex>q_{0,0}</tex> должен быть начальным состоянием <tex>\#_s</tex> машины <tex> m</tex>, символы с <tex>q_{0,1}</tex> по <tex>q_{0,|x|}</tex> &mdash; образовывать цепочку <tex>x</tex>, а оставшиеся <tex>q_{0,i }</tex> &mdash; быть пробелами <tex>B</tex>. Таким образом, <tex>S = Y_{0,0,\#_s} \land Y_{0,1,x_1} \in land \ldots \lbrace land Y_{0,|x|+1 ,B} \land \ldots n \rbrace land Y_{0,t,B}</tex>.::# <tex>T</tex> отвечает за правильный финиш, то есть в МО <tex>q_t</tex> должно присутствовать допускающее состояние <tex>\#_y</tex>, следовательно <tex>T = Y_{t,0,\#_y} \lor Y_{t,1,\#_y} \lor \ldots \lor Y_{t,t,\#_y}</tex>. ::# <tex>N</tex> отвечает за то, что машина <tex>m</tex> делает правильные переходы. <tex>q_{i,j}</tex> зависит только от четырех символов над ним, то есть от <tex>q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}</tex> и <tex>q_{i-1,j+2}</tex>. Тогда для проверки корректности переходов требуется перебрать все четверки символов <tex>q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}</tex> и <tex>q_{i-1,j+2}</tex> из таблицы и проверить, что из них возможно получить символ <tex>q_{i,j}</tex>. Если четверка символов выходит за границу таблицы, то указывается меньшее количество позиций. С учетом того, что машина <tex> x_i m</tex> недетерминирована и требуется устранить возможность раздвоения ее головки, сделаем все возможные выводы о новых символах <tex>q_{i,j \pm 1}</tex>: <br> <tex>N = \land_{i= choose0..t,j=0..t} \land_{c_1 \ldots c_4} (( Y_{i-1,j-1,c_1} \land Y_{i-1,j,c_2} \land Y_{i-1,j+1,c_3} \land Y_{i-1,j+2,c_4} ) \to ((Y_{i,j-1,c_0^`} \lor Y_{i,j-1,c_1^`} \lor \ldots \lor Y_{i,j-1,c_{|\Sigma|+|Q|-1}^`}) \land (Y_{i,j,c_0^`} \lor Y_{i,j,c_1^`} \lor \ldots \lor Y_{i,j,c_{|\Sigma|+|Q|-1}^`}) \land (Y_{i,j+1,c_0^`} \lor Y_{i,j+1,c_1^`} \lor \ldots \lor Y_{i,j+1,c_{|\Sigma|+|Q|-1}^`})))</tex>.::# <tex>C</tex> отвечает за то, что в каждой ячейке находится ровно один символ. Для каждой ячейки <tex>q_{i,j}</tex> проверяется, что только одна переменная <tex>Y_{i,j,c}</tex> принимает значение ''истина''.<br> <tex>C = \lbrace land_{i=0..t,j=0..t} ((Y_{i,j,c_1} \land \lnot Y_{i,j,c_2} \land \ldots \land \lnot Y_{i,j,c_{|\Sigma|+|Q|-1}}) \lor \ldots \lor (Y_{i,j,c_{|\Sigma|+|Q|-1}} \land \lnot Y_{i,j,c_1} \land \ldots \land \lnot Y_{i,j,c_{|\Sigma|+|Q|-2}}))</tex>.:: Мы построили функцию сведения <tex> f: \langle m, x, 1 ^t \rbrace rangle \mapsto \varphi = S \land T \land N \land C</tex>. Она является полиномиальной, так как длина формулы <tex>\varphi</tex> полиномиально зависит от длины входа &mdash; if <tex> |\varphi| = O(xn^2) </tex> == . <br> Покажем, что <tex>\varphi</tex> выполнима тогда и только тогда, когда <tex>\langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} </tex>.:# Пусть <tex>\langle m, x, 1^t \rangle \in \mathrm{BH_{1N}}</tex>, тогда существует допускающая цепочка переходов <tex>q_0 \vdash q_1 \vdash ... \vdash q_t</tex> и можем построить таблицу, аналогичную приведенной выше, следовательно можем найти такое присваивание 0 и 1 переменным <tex>Y_{i,j,c}</tex>, что <tex>\varphi</tex> примет значение ''истина''. return :# Пусть в результате работы функции <tex>f</tex> получили выполнимую формулу <tex>\varphi</tex>, следовательно существует такой набор переменных <tex>Y_{i,j,c}</tex>, что <tex>\varphi</tex> на нем принимает значение ''истина''. Тогда по данному набору можем построить таблицу, по которой восстановим допускающую цепочку переходов <tex>q_0 \vdash q_1 \vdash ... \vdash q_t</tex>. Совершив эти переходы машина <tex>m</tex> перейдет в допускающее состояние за время <tex>t</tex>, следовательно <tex>\langle m, x, 1^t\rangle \in \mathrm{BH_{1N}}</tex>. else return 0:Значит <tex> \mathrm{SAT} \in \mathrm{NPC} </fonttex>, что и требовалось доказать. 

<tex> \mathrm{3SAT} </tex> {{---}} язык булевых формул, заданных в [[КНФ]], таких что каждый дизъюнкт состоит ровно из 3 переменных и для этой булевой формулы существует подстановка, при которой она истинна.  <tex> \mathrm{3SAT} = \lbrace \varphi(x_1 \ldots x_n) \bigm| \varphi </tex> задано в 3КНФ и <tex> \exists x_1 \ldots x_n : \varphi(x_1 \ldots x_n) = 1 \rbrace </tex> {{Теорема|statement= <tex> \mathrm{3SAT} \in \mathrm{NPC} </tex>|proof=#<tex> \mathrm{3SAT} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{3SAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ.# <tex> \mathrm{3SAT} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{CNFSAT} </tex> к задаче <tex> \mathrm{3SAT} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить по булевой формуле в [[КНФ]], булевую формулу в 3-КНФ, такую что <tex> x \in \mathrm{CNFSAT} \Leftrightarrow f(x) \in \mathrm{3SAT} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> Опишем как будет работать функция <tex> f </tex>. <br> Заменим каждый дизъюнкт в <tex> x </tex> на может быть несколько дизъюнктов, которые состоят ровно из трех переменных.## Дизъюнкт содержит не более трех переменных. Тогда возьмем какую-нибудь переменную из этого дизъюнкта и продублируем ее так, чтобы в нем стало ровно 3 переменных. Например: <tex> f(y \lor z) = (y \lor z \lor y) </tex>, <tex> f(y) = (y \lor y \lor y) </tex>## Дизъюнкт содержит больше трех переменных. Пусть он имеет вид: <tex> (x_1 \lor x_2 \lor \ldots \lor x_k) </tex>, создадим новые переменные <tex> z_1, z_2, \ldots, z_{k - 2} </tex>, и тогда <br> <tex> f(x_1 \lor x_2 \lor \ldots \lor x_k) = (x_1~\lor~x_2~\lor~z_1)~\land~(x_3~\lor~\neg{z_1}~\lor~z_2)~\land~\ldots~\land~(x_i~\lor~\neg{z_{i - 2}}~\lor~z_{i - 1})~\land~\ldots~\land~(x_{k - 1}~\lor~x_k~\lor~\neg{z_{k - 2}}) </tex> <br> Можно заметить, что если какое-то <tex> x_i = 1 </tex>, то существует подстановка для <tex> z_1, z_2, \ldots, z_{k - 1} </tex>, такая что <tex> f(x_1 \lor x_2 \lor \ldots \lor x_k)</tex> удовлетворима. Также, если <tex> \forall i : x_i = 0 </tex>, нельзя удовлетворить все скобки, так как каждая скобка удовлетворяется только переменными <tex> z_1, z_2, \ldots, z_{k - 2} </tex>, можно понять, что при выборе значения <tex> z_1 </tex> все переменные восстанавливаются однозначно и значение <tex> z_{k - 2} </tex> нельзя выбрать так, чтобы удовлетворить последние две скобки одновременно. А значит <tex> x \in CNFSAT \Leftrightarrow f(x) \in 3SAT </tex>.#:Заметим, что размер формулы возрос не более чем в три раза, поэтому функция <tex> f </tex> будет работать за полином.:Значит <tex> \mathrm{3SAT} \in \mathrm{NPC} </tex>}}=== NP-полнота раскраски графа поиска максимального независимого множества ===<tex> \mathrm{IND} </tex> {{---}} язык неориентированных графов, таких что в графе есть независимое множество мощности <tex> k </tex>. <tex> \mathrm{IND} =\lbrace \langle G, k \rangle \bigm| \exists H \subset V(G) </tex>, такое что <tex> H </tex> независимо в <tex> G \rbrace </tex> {{Теорема|statement= <tex> \mathrm{IND} \in \mathrm{NPC} </tex>|proof=#<tex> \mathrm{IND} \in \mathrm{NP} </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{IND} </tex>. Она будет недетерминированно выбирать множество вершин мощности <tex> k </tex>, проверять, является ли это множество независимым, это можно сделать за полином, и выдавать ответ.# <tex> \mathrm{IND} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{3SAT} </tex> к задаче <tex> \mathrm{IND} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить по булевой формуле в 3-КНФ, пару <tex> \langle G, k \rangle </tex>, такую что <tex> x \in \mathrm{3SAT} \Leftrightarrow f(x) \in \mathrm{IND} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> Опишем как будет работать функция <tex> f </tex>.## <tex> k </tex> {{---}} количество дизъюнктов в <tex> x </tex>.## Для каждого дизъюнкта создадим по три вершины в графе <tex> G </tex>, каждая из которой будет сопоставлена переменной из этого дизъюнкта. <tex> |V(G)| = 3k </tex>## Соединим вершины из одного дизъюнкта ребрами.## Для всех пар вершин, которые сопоставлены переменным, которые являются отрицаниями друг друга, добавим ребро между этими вершинами.#: Докажем, что <tex> x \in \mathrm{3SAT} \Leftrightarrow \langle G, k \rangle \in \mathrm{IND} </tex>#* Пусть формула <tex> x </tex> удовлетворима. Тогда в каждом дизъюнкте будет будет существовать вершина, что сопоставленная ей переменная истинна. Для каждого дизъюнкта выберем ровно одну такую вершину. Это множество будет мощности <tex> k </tex> и независимым, потому что в каждом дизъюнкте мы выбрали ровно одну переменную и мы не выбрали пару вершин, которые сопоставленны переменным, которые являются отрицаниями друг друга.#* Пусть существует независимое множество мощности <tex> k </tex> в графе <tex> G </tex>. Тогда известно, что для каждого дизъюнкта не может быть выбрано более одной вершины из нее, значит из каждого дизъюнкта выбрана ровно одна вершина, потому что всего вершин {{---}} <tex> k </tex>. Теперь если мы удовлетворим каждую переменную, сопоставленная вершина которой в независимом множестве, вся формула удовлетворится. А каждую переменную можно удовлетворить, потому что в независимом множестве нет пары вершин, которым сопоставлены переменные, которые являются отрицаниями друг друга. Значит формула удовлетворима.: А значит <tex> \mathrm{IND} \in \mathrm{NPC} </tex>.}}

=== NP<tex> \mathrm{VCOVER} </tex> {{---полнота поиска максимальной клики }} язык неориентированных графов, таких что в графе есть вершинное покрытие мощности <tex> k </tex>. <tex> \mathrm{VCOVER} =\lbrace \langle G, k \rangle \bigm| \exists H \subset V(G) : \forall vu \in E(G), (v \in H) \lor (u \in H) \rbrace </tex>{{Лемма|statement =<tex> G </tex> {{---}} неориентированный граф. <tex> H \subset G </tex> является независимым множеством в <tex> G \Rightarrow G \setminus H </tex> является вершинным покрытием в <tex> G </tex>.|proof=* <tex> \Rightarrow </tex>Пусть <tex> H </tex> {{---}} независимое множество. Заметим, что по определению независимого множества <tex> \forall vu \in E(G) : (v \notin H) \lor (u \notin H) </tex>, из чего следует, что <tex> (v \in (G \setminus H)) \lor (u \in (G \setminus H)) </tex>, это значит, что <tex> G \setminus H </tex> {{---}} вершинное покрытие.* <tex> \Leftarrow </tex>Пусть <tex> H </tex> {{---}} вершинное покрытие. Заметим, что <tex> \forall vu \in E(G) : (v \in H) \lor (u \in H) </tex>, из чего следует, что <tex> (v \notin (G \setminus H)) \lor (u \notin (G \setminus H)) </tex>, это значит, что <tex> G \setminus H </tex> {{---}} независимое множество.}} {{Теорема|statement=<tex> \mathrm{VCOVER} \in \mathrm{NPC} </tex>|proof== #<tex> \mathrm{VCOVER} \in \mathrm{NP-полнота поиска гамильтонова цикла } </tex> <br> Можно написать недетерминированную программу <tex>p</tex>, которая распознает язык <tex> \mathrm{VCOVER} </tex>. Она будет недетерминированно выбирать множество вершин мощности <tex> k </tex>, проверять, является ли это множество вершинным покрытием, это можно сделать за полином, и пути в графе ===выдавать ответ.# <tex> \mathrm{VCOVER} \in \mathrm{NPH} </tex> <br>Сведем задачу <tex> \mathrm{IND} </tex> к задаче <tex> \mathrm{VCOVER} </tex>. Построим функцию <tex> f(x) </tex>, которая будет строить паре <tex> \langle G, k \rangle </tex>, пару <tex> \langle H, l \rangle </tex>, такую что <tex> x \in \mathrm{IND} \Leftrightarrow f(x) \in \mathrm{VCOVER} </tex>, причем <tex> |f(x)| \le p(|x|) </tex> для некоторого полинома <tex> p </tex>. <br> <tex> f(\langle G, k \rangle) === NP\langle G, |V(G)| - k \rangle </tex> <br> Из доказанной выше леммы, следует, что <tex> \langle G, k \rangle \in \mathrm{IND} \Leftrightarrow \langle G, |V(G)| -полнота задачи о рюкзаке ===k \rangle \in \mathrm{VCOVER} </tex>}}