38
правок
Изменения
изменил форматирование в соответствии с новыми правилами ведения конспектов
тогда окажется, что P = NP.
Мы рассмотрим некоторые языки и докажем их NP-полноту. Начнем мы с языка <tex> \mathrm{BH_{1N}} </tex>, так как к нему несложно сводятся все языки из NP.
Потом с помощью сведений по Карпу будем сводить уже известные языки из NPC к новым языкам, тем самым доказывая их NP-трудность, а потом и NP-полноту.
Доказательство NP-полноты будет состоять из двух пунктов: доказательство NP-трудности и принадлежности языка классу NP.
== NP-полнота <tex> \mathrm{BH_{1N}} </tex> ==<tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает 1 за время <tex> T(m, x) \le t </tex>.
<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>
{{Теорема
|statement=<tex> \mathrm{BH_{1N}} \in \mathrm{NPC } </tex>
|proof=
# <tex> \mathrm{BH_{1N}} \in \mathrm{NPH } </tex># <tex> \mathrm{BH_{1N}} \in \mathrm{NP } </tex>
}}
== NP-полнота <tex> \mathrm{SAT } </tex> ==<tex> \mathrm{SAT }</tex> {{---}} язык булевых формул из <tex> n </tex> переменных, для которых существует подстановка, при которой формула истинна.
<tex> \mathrm{SAT } = \lbrace \varphi\ \bigm|\ \exists x : \varphi(x) = 1 \rbrace </tex>
{{Теорема
|author=Кук
|statement=<tex> \mathrm{SAT }\in \mathrm{NPC } </tex>
|proof=
# <tex> \mathrm{SAT }\in \mathrm{NPH } </tex># <tex> \mathrm{SAT }\in \mathrm{NP } </tex> <br>Можно написать недетерминированную программу <tex> p</tex>, которая распознает язык <tex> \mathrm{SAT } </tex>. Она будет недетерминированно выбирать подстановку, проверять истинна ли формула при такой подстановке и выдавать ответ:
<font size = 2>
<tex>p(\varphi)</tex>
