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

Эта статья находится в разработке!

Введение

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

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

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] возращает [math]1[/math] за время [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]

[math] \mathrm{BH_{1N}} \in \mathrm{NPH} [/math] Нужно доказать, что [math] \forall \mathrm{L} \in \mathrm{NP} [/math] существует полиномиальное сведение по Карпу к языку [math] \mathrm{BH_{1N}} [/math]. Рассмотрим произвольный язык [math] \mathrm{L} \in \mathrm{NP} [/math]. Для него существует машина Тьюринга [math] m [/math] и полином [math] p(x) [/math], такие что [math] T(m, x) \le p(|x|), \mathrm{L}(m) = \mathrm{L} [/math]. Докажем, что [math] \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} [/math]. Рассмотрим функцию [math] f(x) = \langle m, x, 1^{p(|x|)} \rangle [/math], по входным данным возвращающую тройку из описанной выше машины Тьюринга, входных данных и времени [math] p(|x|)[/math] в унарной системе счисления. Проверим, что [math] x \in \mathrm{L} \Leftrightarrow f(x) \in \mathrm{BH_{1N}} [/math]. Пусть [math] x \in L [/math]. Тогда [math] m(x) = 1 [/math] за время не более [math] p(|x|) [/math], а значит [math]\langle m,x, 1^{p(|x|)} \rangle = f(x) \in \mathrm{BH_{1N}} [/math]. Пусть [math]x \not\in L[/math]. Тогда [math]m(x) = 0[/math] и [math]\langle m,x, 1^{p(|x|)} \rangle = f(x) \notin \mathrm{BH_{1N}} [/math]. Это значит, что [math] \forall \mathrm{L} \in \mathrm{NP}\ \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} [/math], и из этого следует, что [math] \mathrm{BH_{1N}} \in \mathrm{NPH} [/math]. [math] \mathrm{BH_{1N}} \in \mathrm{NP} [/math] Можно написать недетерминированную программу, которая будет по [math] \langle m, x, 1^t \rangle [/math] моделировать [math] t [/math] шагов [math] m [/math] на входе [math] x [/math], выбирая недетерминированно соответствующие недетерминированные переходы, и если машина за это время допустила слово, то только тогда [math] \langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} [/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]

[math] \mathrm{SAT}\in \mathrm{NPH} [/math] [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] = choose[math] \lbrace 0, 1 \rbrace [/math]; if [math] \varphi(x) [/math] == 1: return 1 else return 0

[math]\triangleleft[/math]

Ссылки

• Класс P
• Классы NP и Σ₁
• Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи