Примеры NP-полных языков. Теорема Кука

2012-04-15T10:20:25Z

109.188.214.208:

{{В разработке}}

== Введение ==
В этой статье мы рассмотрим класс NP-полных языков {{---}} NPC.
NPC является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс P,
тогда окажется, что P = NP.

Мы рассмотрим некоторые языки и докажем их NP-полноту. Начнем мы с языка <tex> BH_{1N} </tex>, так как к нему несложно сводятся все языки из NP.
Потом с помощью сведений по Карпу будем сводить уже известные языки из NPC к новым языкам, тем самым доказывая их NP-трудность, а потом и NP-полноту.
Доказательство NP-полноты будет состоять из двух пунктов: доказательство NP-трудности и принадлежности языка классу NP.

== NP-полнота <tex> BH_{1N} </tex> ==
<tex> 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> BH_{1N} = \lbrace \langle m, x, 1^t \rangle | m </tex> {{---}} недерминированная машина Тьюринга, <tex> m(x) = 1, T(m,x) \le t \rbrace </tex>
{{Теорема
|statement=<tex> BH_{1N} \in NPC </tex>
|proof=
# <tex> BH_{1N} \in NPH </tex>
# <tex> BH_{1N} \in NP </tex>
}}

== NP-полнота <tex> SAT </tex> ==
<tex> SAT </tex> {{---}} язык булевых формул, для которых существует подстановка, при которой формула истинна.

<tex> SAT = \lbrace \varphi\ |\ \exists x : \varphi(x) = 1 \rbrace </tex>
{{Теорема
|author=Кук
|statement=<tex> SAT \in NPC </tex>
|proof=
# <tex> SAT \in NPH </tex>
# <tex> SAT \in NP </tex> <br>Можно написать недетерминированную программу, которая распознает язык SAT. Она будет недетерминированно выбирать подстановку, проверять истинна ли формула при такой подстановке и выдавать ответ.
}}

Викиконспекты - Вклад участника [ru]

Примеры NP-полных языков. Теорема Кука