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

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

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

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

== NP-полнота <tex> BH_{1N} </tex> ==
BH_{1N} {{---}} язык троек <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 \rbrace </tex>
{{Теорема
|statement=<tex> BH_{1N} \in NPC </tex>
|proof=
# <tex> BH_{1N} \in NPH </tex>
# <tex> BH_{1N} \in NP </tex>
}}