Теорема Кука

Определение

Проблема [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]\phi\,\![/math], что она выполнима тогда, и только тогда, когда [math]m\,\![/math], получив на вход [math]x\,\![/math], делает не более [math]t\,\![/math] шагов и допускает это слово.

В любой момент времени мгновенное описание (МО) [math]m\,\![/math] есть строка [math]z\#_qyb[/math], где [math]b\,\![/math] — строка, состоящая из такого количества пробелов, чтобы длина всего МО была [math]t + 1.\,\![/math] Соответственно, начальное МО задаётся так : [math]\#_sxb\,\![/math] ([math]b\,\![/math] может быть пустой). Если же [math]|x| \gt t\,\![/math], то будем считать, что на ленту записаны лишь первые [math]t\,\![/math] символов, ведь [math]m\,\![/math] не может обработать большее количество символов за [math]t\,\![/math] шагов.

Также нам удобно считать, что все вычисления проходят ровно за [math]t + 1\,\![/math] шагов, даже если мы попали в допускающее состояние раньше. То есть, мы разрешим переход [math]q \vdash q[/math], если в МО [math]q\,\![/math] есть допускающее состояние, так что, чтобы проверить, допустила ли машина слово, надо лишь проверить наличие допускающего состояния в МО [math]q_t\,\![/math].

Тогда процесс работы машины [math]m\,\![/math] на входе [math]x\,\![/math], то есть цепочка переходов [math]q_0 \vdash q_1 \vdash ... \vdash q_t[/math] может быть представлен следующей таблицей :

Процесс работы машины [math]m\,\![/math] на входе [math]x\,\![/math]

MO	0	1	...					...	t
[math]q_0\,\![/math]	[math]q_{0, 0}\,\![/math]	[math]q_{0, 1}\,\![/math]							[math]q_{0, t}\,\![/math]
[math]q_1\,\![/math]	[math]q_{1, 0}\,\![/math]	[math]q_{1, 1}\,\![/math]							[math]q_{1, t}\,\![/math]
...
[math]q_i\,\![/math]				[math]q_{i, j - 1}\,\![/math]	[math]q_{i, j}\,\![/math]	[math]q_{i, j + 1\,\!}[/math]	[math]q_{i, j + 2\,\!}[/math]
[math]q_{i + 1}\,\![/math]				[math]q_{i, j - 1}\,\![/math]	[math]q_{i, j}\,\![/math]	[math]q_{i, j + 1\,\!}[/math]
...
[math]q_t\,\![/math]	[math]q_{t, 0}\,\![/math]	[math]q_{t, 1}\,\![/math]							[math]q_{t, t}\,\![/math]

Каждый элемент таблицы [math]q_{i, j}\in \Sigma \cup Q[/math]. И для каждого такого элемента заведём [math]|\Sigma| + |Q|\,\![/math] переменных [math]Y_{i, j, c} = [q_{i, j} = c]\ \forall c \in \Sigma \cup Q\,\![/math]

Общий вид формулы : [math]\phi = S \land T \land N \land C[/math]