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

Материал из Викиконспекты
Версия от 10:38, 4 июня 2012; Niyaz.nigmatullin (обсуждение | вклад) (изменил форматирование в соответствии с новыми правилами ведения конспектов)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Введение

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

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

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

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

[math] \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \bigm| m [/math] — недерминированная машина Тьюринга, [math] m(x) = 1, T(m,x) \le t \rbrace [/math]

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

NP-полнота [math] \mathrm{SAT} [/math]

[math] \mathrm{SAT}[/math] — язык булевых формул из [math] n [/math] переменных, для которых существует подстановка, при которой формула истинна.

[math] \mathrm{SAT} = \lbrace \varphi\ \bigm|\ \exists x : \varphi(x) = 1 \rbrace [/math]

Теорема (Кук):
[math] \mathrm{SAT}\in \mathrm{NPC} [/math]
Доказательство:
[math]\triangleright[/math]
  1. [math] \mathrm{SAT}\in \mathrm{NPH} [/math]
  2. [math] \mathrm{SAT}\in \mathrm{NP} [/math]
    Можно написать недетерминированную программу [math] p[/math], которая распознает язык [math] \mathrm{SAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять истинна ли формула при такой подстановке и выдавать ответ:

 [math]p(\varphi)[/math]
   for [math] i \in \lbrace 1 \ldots n \rbrace [/math]:
     [math] x_i [/math] = random(2);
   if [math] \varphi(x) [/math] == 1:
     return 1
   else
     return 0
[math]\triangleleft[/math]

Другие примеры NP-полных языков

NP-полнота 3-SAT

NP-полнота раскраски графа

NP-полнота поиска минимального вершинного покрытия в графе

NP-полнота поиска максимальной клики в графе

NP-полнота поиска гамильтонова цикла и пути в графе

NP-полнота задачи о рюкзаке