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

Материал из Викиконспекты
Версия от 23:51, 14 апреля 2012; Niyaz.nigmatullin (обсуждение | вклад) (Новая страница: «{{В разработке}} == Введение == В этой статье мы рассмотрим класс NP-полных языков {{---}} NPC. NPC я...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Введение

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

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

NP-полнота [math] BH_{1N} [/math]

BH_{1N} — язык троек [math] \langle m, x, 1^t \rangle [/math], таких что недетерминированная машина Тьюринга [math] m [/math] на входной строке [math] x [/math] возращает 1 за время [math] T(m, x) \le t [/math].

[math] BH_{1N} = \lbrace \langle m, x, 1^t \rangle \rbrace [/math]

Теорема:
[math] BH_{1N} \in NPC [/math]
Доказательство:
[math]\triangleright[/math]
  1. [math] BH_{1N} \in NPH [/math]
  2. [math] BH_{1N} \in NP [/math]
[math]\triangleleft[/math]