Теорема Кука

Определение

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

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

Теорема Кука

Теорема (Кук):

[math] \mathrm{SAT}\in \mathrm{NPC} [/math]

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

[math]\triangleright[/math]

[math] \mathrm{SAT}\in \mathrm{NP} [/math] Можно написать недетерминированную программу [math]p[/math], которая распознает язык [math] \mathrm{SAT} [/math]. Она будет недетерминированно выбирать подстановку, проверять, истинна ли формула при такой подстановке, и выдавать ответ. [math] \mathrm{SAT}\in \mathrm{NPH} [/math] Теперь докажем, что [math] \mathrm{SAT}\in \mathrm{NPH} [/math]. Для этого сведём задачу [math] \mathrm{BH_{1N}} [/math], которая [math] \mathrm{NP} [/math]-полна, к [math] \mathrm{SAT} [/math]. Тогда получится, что любой язык из [math] \mathrm{NP} [/math] может быть сведен по Карпу к [math] \mathrm{BH_{1N}} [/math], и, по транзитивности сведения по Карпу, к [math] \mathrm{SAT} [/math]. По определению языка [math] \mathrm{BH_{1N}} [/math], у нас есть: недетерминированная машина Тьюринга [math]m[/math], причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы входное слово [math]x[/math] время [math]t[/math], заданное в унарной системе счисления. Нам же надо построить такую булеву формулу [math]\varphi[/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[/math], если в МО [math]q[/math] есть допускающее состояние, так что, чтобы проверить, допустила ли машина слово, надо лишь проверить наличие допускающего состояния в МО [math]q_t[/math]. Тогда процесс работы машины [math]m[/math] на входе [math]x[/math], то есть цепочка переходов [math]q_0 \vdash q_1 \vdash \ldots \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]\varphi = S \land T \land N \land C[/math]. [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]. [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]. [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 (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]. [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 \varphi = S \land T \land N \land C[/math]. Она является полиномиальной, так как длина формулы [math]\varphi[/math] полиномиально зависит от длины входа — [math]|\varphi| = O(n^2)[/math]. Покажем, что [math]\varphi[/math] выполнима тогда и только тогда, когда [math]\langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} [/math]. Пусть [math]\langle m, x, 1^t \rangle \in \mathrm{BH_{1N}}[/math], тогда существует допускающая цепочка переходов [math]q_0 \vdash q_1 \vdash ... \vdash q_t[/math] и можем построить таблицу, аналогичную приведенной выше, следовательно можем найти такое присваивание 0 и 1 переменным [math]Y_{i,j,c}[/math], что [math]\varphi[/math] примет значение истина. Пусть в результате работы функции [math]f[/math] получили выполнимую формулу [math]\varphi[/math], следовательно существует такой набор переменных [math]Y_{i,j,c}[/math], что [math]\varphi[/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 \in \mathrm{BH_{1N}}[/math]. Значит [math] \mathrm{SAT} \in \mathrm{NPC} [/math], что и требовалось доказать.

[math]\triangleleft[/math]

См. также

• NP-полнота BH1N
• Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
• Недетерминированные вычисления