Теорема Кука

Определение

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

Докажем, что эта проблема NP-полна.

Формулировка теоремы Кука

SAT ∈ NPC

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

SAT ∈ NPC, если

• SAT ∈ NP
• SAT ∈ NPH

Доказательство того, что SAT ∈ NP

Прежде всего докажем, что SAT ∈ NP.

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

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

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

Доказательство того, что SAT ∈ NPH

Теперь докажем, что SAT ∈ NPH. Для этого сведём проблему BH_1N, которая, как нам известно, NP-полна, к проблеме SAT. Тогда получится, что любая проблема из NP может быть сведена по Карпу к проблеме BH_1N, и, по транзитивности сведения по Карпу, к SAT.

По условию проблемы BH_1N, у нас есть недетерминированная машина Тьюринга [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]|x| \gt t[/math], то будем считать, что на ленту записаны лишь первые [math]t[/math] символов, ведь [math]m[/math] не может обработать большее количество символов за [math]t[/math] шагов.

Также нам удобно считать, что все вычисления проходят ровно за [math]t + 1[/math] шагов, даже если мы попали в допускающее состояние раньше. То есть, мы разрешим переход [math]q \vdash q_t[/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+1, j - 1}[/math]	[math]q_{i+1, j}[/math]	[math]q_{i+1, 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].

1. [math]S[/math] отвечает за правильный старт, то есть символ [math]q_{0,0}[/math] должен быть начальным состоянием [math]\#_s[/math] машины [math]m[/math], символы с [math]q_{0,1}[/math] по [math]q_{0,|x|}[/math] — образовывать цепочку [math]x[/math], а оставшиеся [math]q_{0,i}[/math] — быть пробелами [math]B[/math]. Таким образом, [math]S = Y_{0,0,\#_s} \land Y_{0,1,x_1} \land \ldots \land Y_{0,|x|+1,B} \land \ldots \land Y_{0,t,B}[/math].
2. [math]T[/math] отвечает за правильный финиш, то есть в МО [math]q_t[/math] должно присутствовать допускающее состояние [math]\#_y[/math], следовательно [math]T = Y_{t,0,\#_y} \lor Y_{t,1,\#_y} \lor \ldots \lor Y_{t,t,\#_y}[/math].
3. [math]N[/math] отвечает за то, что машина [math]m[/math] делает правильные переходы. [math]q_{i,j}[/math] зависит только от четырех символов над ним, то есть от [math]q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}[/math] и [math]q_{i-1,j+2}[/math]. Тогда для проверки корректности переходов требуется перебрать все четверки символов [math]q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}[/math] и [math]q_{i-1,j+2}[/math] из таблицы и проверить, что из них возможно получить символ [math]q_{i,j}[/math]. Если четверка символов выходит за границу таблицы, то указывается меньшее количество позиций. С учетом того, что машина [math]m[/math] недетерминирована и требуется устранить возможность раздвоения ее головки, сделаем все возможные выводы о новых символах [math]q_{i,j \pm 1}[/math]: [math]N = \land_{i=0..t,j=0..t} \land_{c_1 \ldots c_4} (( Y_{i-1,j-1,c_1} \land Y_{i-1,j,c_2} \land Y_{i-1,j+1,c_3} \land Y_{i-1,j+2,c_4} ) \to ((Y_{i,j-1,c_0^`} \lor Y_{i,j-1,c_1^`} \lor \ldots \lor Y_{i,j-1,c_{|\Sigma|+|Q|-1}^`}) \land[/math] [math]\land (Y_{i,j,c_0^`} \lor Y_{i,j,c_1^`} \lor \ldots \lor Y_{i,j,c_{|\Sigma|+|Q|-1}^`}) \land (Y_{i,j+1,c_0^`} \lor Y_{i,j+1,c_1^`} \lor \ldots \lor Y_{i,j+1,c_{|\Sigma|+|Q|-1}^`})))[/math].
4. [math]C[/math] отвечает за то, что в каждой ячейке находится ровно один символ. Для каждой ячейки [math]q_{i,j}[/math] проверяется, что только одна переменная [math]Y_{i,j,c}[/math] принимает значение истина. [math]C = \land_{i=0..t,j=0..t} ((Y_{i,j,c_1} \land \lnot Y_{i,j,c_2} \land \ldots \land \lnot Y_{i,j,c_{|\Sigma|+|Q|-1}}) \lor \ldots \lor (Y_{i,j,c_{|\Sigma|+|Q|-1}} \land \lnot Y_{i,j,c_1} \land \ldots \land \lnot Y_{i,j,c_{|\Sigma|+|Q|-2}}))[/math].

Мы построили функцию сведения [math]f: \langle m, x, 1^t \rangle \mapsto \phi = S \land T \land N \land C[/math]. Она является полиномиальной, так как длина формулы [math]\phi[/math] полиномиально зависит от длины входа — [math]|\phi| = O(n^2)[/math]. Покажем, что [math]\phi[/math] выполнима тогда и только тогда, когда [math]\langle m, x, 1^t \rangle[/math] ∈ BH_1N.

1. Пусть [math]\langle m, x, 1^t \rangle[/math] ∈ BH_1N, тогда существует допускающая цепочка переходов [math]q_0 \vdash q_1 \vdash ... \vdash q_t[/math] и можем построить таблицу, аналогичную приведенной выше, следовательно можем найти такое присваивание 0 и 1 переменным [math]Y_{i,j,c}[/math], что [math]\phi[/math] примет значение истина.
2. Пусть в результате работы функции [math]f[/math] получили выполнимую формулу [math]\phi[/math], следовательно существует такой набор переменных [math]Y_{i,j,c}[/math], что [math]\phi[/math] на нем принимает значение истина. Тогда по данному набору можем построить таблицу, по которой восстановим допускающую цепочку переходов [math]q_0 \vdash q_1 \vdash ... \vdash q_t[/math]. Совершив эти переходы машина [math]m[/math] перейдет в допускающее состояние за время [math]t[/math], следовательно [math]\langle m, x, 1^t\rangle[/math] ∈ BH_1N.

Значит, SAT ∈ NPH и из доказанного ранее следует, что SAT ∈ NPC, что и требовалось доказать.

Внешние ссылки

• Хопкрофт Дж., Мотвани Р., Ульман Дж., "Введение в теорию автоматов, языков и вычислений"