Теорема Кука

Определение

Проблема [math]SAT = \{\phi(x_1, ..., x_n)\ |\ \exists \{y_1, ..., y_n\} : \phi(y_1, ..., y_n) = 1\}[/math] — проблема выполнимости булевых формул.

Докажем, что эта проблема [math]NP\,\![/math]-полна.

Формулировка

Теорема Кука гласит, что [math]SAT \in NPC.[/math]

Доказательство

[math]SAT \in NPC[/math], если

• [math]SAT \in NP[/math]
• [math]SAT \in NPH[/math]

Прежде всего докажем, что [math]SAT \in NP.[/math]

Так как [math]NP = \Sigma_1\,\![/math], то достаточно показать, что [math]SAT \in \Sigma_1[/math]

В качестве сертификата берём набор нулей и единиц в количестве [math]n\,\![/math] штук, соответствующих значениям аргументов функции [math]\phi\,\![/math]. Длина этого сертификата явно будет меньше или равна, чем полином от длины строки, кодирующей формулу [math]\phi\,\![/math].

Верификатор просто подставит эти значения в формулу [math]\phi\,\![/math] и выдаст значение формулы на данном входе. Таким образом, если формула действительно удовлетворима, то для неё найдётся такой сертификат, на котором она, и, соответственно, верификатор, выдадут единицу.

Если же у нас существует такой сертификат [math]y\,\![/math], на котором верификатор выдаёт единицу, то, значит, и формула является удовлетворимой.

Теперь докажем, что [math]SAT \in NPH.[/math] Для этого сведём проблему [math]BH_{1N}\,\![/math], которая, как нам известно, [math]NP\,\![/math]-полна, к проблеме [math]SAT.\,\![/math] Тогда получится, что любая проблема из [math]NP\,\![/math] может быть сведена по Карпу к проблеме [math]BH_{1N}\,\![/math], и, соответственно, к [math]SAT.\,\![/math]

По условию проблемы [math]BH_{1N}\,\![/math], у нас есть недетерминированная машина Тьюринга [math]m\,\![/math], причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы, входное слово [math]x\,\![/math] и время [math]t\,\![/math], заданное в унарной системе счисления. В любой момент времени мгновенное описание (МО) [math]m\,\![/math] есть строка [math]z\#_qyb[/math], где [math]b\,\![/math] — строка, состоящая из такого количества пробелов, чтобы длина всего МО была [math]t + 1.\,\![/math]