38
правок
Изменения
Новая страница: «{{В разработке}} == Введение == В этой статье мы рассмотрим класс NP-полных языков {{---}} NPC. NPC я...»
{{В разработке}}
== Введение ==
В этой статье мы рассмотрим класс 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>
}}
== Введение ==
В этой статье мы рассмотрим класс 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>
}}
