Изменения

# <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> может быть представлен следующей таблицей :

<tex> \mathrm{CNFSAT} </tex>{{---}} язык булевых формул, заданных в [[КНФ]], таких что для них существует подстановка, при которой формула истинна.

<tex> \mathrm{3SAT} </tex>{{---}} язык булевых формул, заданных в [[КНФ]], таких что каждый дизъюнкт состоит ровно из 3 переменных и для этой булевой формулы существует подстановка, при которой она истинна.

<tex> \mathrm{IND} </tex>{{---}} язык неориентированных графов, таких что в графе есть независимое множество величины мощности <tex> k </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>}}