Теорема Кука — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
Строка 63: Строка 63:
 
# <tex>S</tex> отвечает за правильный старт, то есть символ <tex>q_{0,0}</tex> должен быть начальным состоянием <tex>\#_s</tex> машины <tex>m</tex>, символы с <tex>q_{0,1}</tex> по <tex>q_{0,|x|}</tex> &mdash; образовывать цепочку <tex>x</tex>, а оставшиеся <tex>q_{0,i}</tex> &mdash; быть пробелами <tex>B</tex>. Таким образом, <tex>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}</tex>.
 
# <tex>S</tex> отвечает за правильный старт, то есть символ <tex>q_{0,0}</tex> должен быть начальным состоянием <tex>\#_s</tex> машины <tex>m</tex>, символы с <tex>q_{0,1}</tex> по <tex>q_{0,|x|}</tex> &mdash; образовывать цепочку <tex>x</tex>, а оставшиеся <tex>q_{0,i}</tex> &mdash; быть пробелами <tex>B</tex>. Таким образом, <tex>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}</tex>.
 
# <tex>T</tex> отвечает за правильный финиш, то есть в МО <tex>q_t</tex> должно присутствовать допускающее состояние <tex>\#_y</tex>, следовательно <tex>T = Y_{t,0,\#_y} \lor Y_{t,1,\#_y} \lor \ldots \lor Y_{t,t,\#_y}</tex>.
 
# <tex>T</tex> отвечает за правильный финиш, то есть в МО <tex>q_t</tex> должно присутствовать допускающее состояние <tex>\#_y</tex>, следовательно <tex>T = Y_{t,0,\#_y} \lor Y_{t,1,\#_y} \lor \ldots \lor Y_{t,t,\#_y}</tex>.
# <tex>N</tex> отвечает за то, что машина <tex>m</tex> делает правильные переходы. <tex>q_{i,j}</tex> зависит только от четырех символов над ним, то есть от <tex>q_{i-1,j-1}</tex>, <tex>q_{i-1,j}</tex>, <tex>q_{i-1,j+1}</tex> и <tex>q_{i-1,j+2}</tex>. Тогда для проверки корректности переходов требуется перебрать все четверки символов <tex>q_{i-1,j-1}</tex>, <tex>q_{i-1,j}</tex>, <tex>q_{i-1,j+1}</tex> и <tex>q_{i-1,j+2}</tex> из таблицы и проверить, что из них возможно получить символ <tex>q_{i,j}</tex>. Если четверка символов выходит за границу таблицы, то указывается меньшее количество позиций. <tex>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,c_1^`} \lor Y_{i,j,c_2^`} \lor \ldots \lor Y_{i,j,c_{|\Sigma|-1}^`}))</tex>.
+
# <tex>N</tex> отвечает за то, что машина <tex>m</tex> делает правильные переходы. <tex>q_{i,j}</tex> зависит только от четырех символов над ним, то есть от <tex>q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}</tex> и <tex>q_{i-1,j+2}</tex>. Тогда для проверки корректности переходов требуется перебрать все четверки символов <tex>q_{i-1,j-1}, q_{i-1,j}, q_{i-1,j+1}</tex> и <tex>q_{i-1,j+2}</tex> из таблицы и проверить, что из них возможно получить символ <tex>q_{i,j}</tex>. Если четверка символов выходит за границу таблицы, то указывается меньшее количество позиций. <tex>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,c_1^`} \lor Y_{i,j,c_2^`} \lor \ldots \lor Y_{i,j,c_{|\Sigma|-1}^`}))</tex>.
 
# <tex>C</tex> отвечает за то, что в каждой ячейке находится ровно один символ. Для каждой ячейки <tex>q_{i,j}</tex> проверяется, что только одна переменная <tex>Y_{i,j,c}</tex> принимает значение ''истина''. <tex>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|-1}}) \lor \ldots \lor (Y_{i,j,c_{|\Sigma|-1}} \land \lnot Y_{i,j,c_1} \land \ldots \land \lnot Y_{i,j,c_{|\Sigma|-2}}))</tex>.
 
# <tex>C</tex> отвечает за то, что в каждой ячейке находится ровно один символ. Для каждой ячейки <tex>q_{i,j}</tex> проверяется, что только одна переменная <tex>Y_{i,j,c}</tex> принимает значение ''истина''. <tex>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|-1}}) \lor \ldots \lor (Y_{i,j,c_{|\Sigma|-1}} \land \lnot Y_{i,j,c_1} \land \ldots \land \lnot Y_{i,j,c_{|\Sigma|-2}}))</tex>.
  
Мы построили функцию сведения <tex>f: <m, x, 1^t> \mapsto \phi = S \land T \land N \land C</tex>. Она является полиномиальной, так как длина формулы <tex>\phi</tex> полиномиально зависит от <tex>|1^t| = t</tex>, а именно: <tex>|\phi| = O(t^3)</tex>.
+
Мы построили функцию сведения <tex>f: \langle m, x, 1^t \rangle \mapsto \phi = S \land T \land N \land C</tex>. Она является полиномиальной, так как длина формулы <tex>\phi</tex> полиномиально зависит от <tex>|1^t| = t</tex>, а именно: <tex>|\phi| = O(t^3)</tex>.
Покажем, что <tex>\phi</tex> выполнима тогда и только тогда, когда <tex><m, x, 1^t> \in BH_{1N}</tex>.
+
Покажем, что <tex>\phi</tex> выполнима тогда и только тогда, когда <tex>\langle m, x, 1^t \rangle \in BH_{1N}</tex>.
  
# Пусть <tex><m, x, 1^t> \in BH_{1N}</tex>, тогда существует допускающая цепочка переходов <tex>q_0 \vdash q_1 \vdash ... \vdash q_t</tex> (в МО <tex>q_t</tex> присутствует допускающее состояние <tex>\#_y</tex>), следовательно можем найти такое присваивание 0 и 1 переменным <tex>Y_{i,j,c}</tex>, что <tex>\phi</tex> примет значение ''истина''.
+
# Пусть <tex>\langle m, x, 1^t \rangle \in BH_{1N}</tex>, тогда существует допускающая цепочка переходов <tex>q_0 \vdash q_1 \vdash ... \vdash q_t</tex> (в МО <tex>q_t</tex> присутствует допускающее состояние <tex>\#_y</tex>), следовательно можем найти такое присваивание 0 и 1 переменным <tex>Y_{i,j,c}</tex>, что <tex>\phi</tex> примет значение ''истина''.
# Пусть в результате работы функции <tex>f</tex> получили выполнимую формулу <tex>\phi</tex>, следовательно существует такой набор переменных <tex>Y_{i,j,c}</tex>, что <tex>\phi</tex> на нем принимает значение ''истина''. Тогда можем по данному набору построить таблицу, аналогичную приведенной выше, по которой можно восстановить допускающую цепочку переходов <tex>q_0 \vdash q_1 \vdash ... \vdash q_t</tex>. Совершив эти переходы машина <tex>m</tex> перейдет в допускающее состояние за время <tex>t</tex>, следовательно <tex><m, x, 1^t> \in BH_{1N}</tex>.
+
# Пусть в результате работы функции <tex>f</tex> получили выполнимую формулу <tex>\phi</tex>, следовательно существует такой набор переменных <tex>Y_{i,j,c}</tex>, что <tex>\phi</tex> на нем принимает значение ''истина''. Тогда можем по данному набору построить таблицу, аналогичную приведенной выше, по которой можно восстановить допускающую цепочку переходов <tex>q_0 \vdash q_1 \vdash ... \vdash q_t</tex>. Совершив эти переходы машина <tex>m</tex> перейдет в допускающее состояние за время <tex>t</tex>, следовательно <tex>\langle m, x, 1^t\rangle \in BH_{1N}</tex>.
  
 
Значит, <tex>SAT \in NPH</tex> и из доказанного ранее следует,что <tex>SAT \in NPC</tex>.
 
Значит, <tex>SAT \in NPH</tex> и из доказанного ранее следует,что <tex>SAT \in NPC</tex>.
  
 
Теорема доказана.
 
Теорема доказана.

Версия 12:51, 16 марта 2010

Определение

Проблема [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]\mathbf{SAT \in NP}[/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]\mathbf{SAT \in NPH}[/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]|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].

  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]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,c_1^`} \lor Y_{i,j,c_2^`} \lor \ldots \lor Y_{i,j,c_{|\Sigma|-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|-1}}) \lor \ldots \lor (Y_{i,j,c_{|\Sigma|-1}} \land \lnot Y_{i,j,c_1} \land \ldots \land \lnot Y_{i,j,c_{|\Sigma|-2}}))[/math].

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

  1. Пусть [math]\langle m, x, 1^t \rangle \in BH_{1N}[/math], тогда существует допускающая цепочка переходов [math]q_0 \vdash q_1 \vdash ... \vdash q_t[/math] (в МО [math]q_t[/math] присутствует допускающее состояние [math]\#_y[/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 \in BH_{1N}[/math].

Значит, [math]SAT \in NPH[/math] и из доказанного ранее следует,что [math]SAT \in NPC[/math].

Теорема доказана.