Теорема Кука — различия между версиями
Alexey (обсуждение | вклад) (→Доказательство: часть 2) |
Alexey (обсуждение | вклад) (→Доказательство: часть 2) |
||
Строка 62: | Строка 62: | ||
<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</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>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>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><m, x, 1^t> \in BH_{1N}</tex>. | ||
+ | |||
+ | 1) Пусть <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>, следовательно можем построить таблицу, аналогичную приведенной выше, а значит можем построить выполнимую формулу <tex>\phi</tex>. | ||
+ | |||
+ | 2) Пусть в результате работы функции <tex>f</tex> получили выполнимую формулу <tex>\phi</tex>, следовательно существует такой набор переменных <tex>Y_{i,j,c}</tex>, что <tex>\phi</tex> на нем принимает значение <tex>1</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>SAT \in NPH</tex> и из доказанного ранее следует,что <tex>SAT \in NPC</tex>. | ||
+ | |||
+ | Теорема доказана. |
Версия 01:16, 16 марта 2010
Определение
Проблема
— проблема выполнимости булевых формул.Докажем, что эта проблема
-полна.Формулировка
Теорема Кука гласит, что
Доказательство
, если
Прежде всего докажем, что
Так как
, то достаточно показать, чтоВ качестве сертификата берём набор нулей и единиц в количестве
штук, соответствующих значениям аргументов функции . Длина этого сертификата явно будет меньше или равна, чем полином от длины строки, кодирующей формулу .Верификатор просто подставит эти значения в формулу
и выдаст значение формулы на данном входе. Таким образом, если формула действительно удовлетворима, то для неё найдётся такой сертификат, на котором она, и, соответственно, верификатор, выдадут единицу.Если же у нас существует такой сертификат
, на котором верификатор выдаёт единицу, то, значит, и формула является удовлетворимой.Теперь докажем, что
Для этого сведём проблему , которая, как нам известно, -полна, к проблеме Тогда получится, что любая проблема из может быть сведена по Карпу к проблеме , и, по транзитивности сведения по Карпу, кПо условию проблемы
, у нас есть недетерминированная машина Тьюринга , причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы, входное слово и время , заданное в унарной системе счисления. Нам же надо построить такую булеву формулу , что она выполнима тогда, и только тогда, когда , получив на вход , делает не более шагов и допускает это слово.В любой момент времени мгновенное описание (МО)
есть строка , где — строка, состоящая из такого количества пробелов, чтобы длина всего МО была Соответственно, начальное МО задаётся так : . Если же , то будем считать, что на ленту записаны лишь первые символов, ведь не может обработать большее количество символов за шагов.Также нам удобно считать, что все вычисления проходят ровно за
шагов, даже если мы попали в допускающее состояние раньше. То есть, мы разрешим переход , если в МО есть допускающее состояние, так что, чтобы проверить, допустила ли машина слово, надо лишь проверить наличие допускающего состояния в МО .Тогда процесс работы машины
на входе , то есть цепочка переходов может быть представлен следующей таблицей :MO | 0 | 1 | ... | ... | t | ||||
---|---|---|---|---|---|---|---|---|---|
... | |||||||||
... | |||||||||
Каждый элемент таблицы
. И для каждого такого элемента заведём переменныхОбщий вид формулы :
.отвечает за правильный старт, то есть символ должен быть начальным состоянием машины , символы с по — образовывать цепочку , а оставшиеся — быть пробелами . Таким образом, .
отвечает за правильный финиш, то есть в должно присутствовать допускающее состояние , следовательно .
отвечает за то, что машина делает правильные переходы. зависит только от четырех символов над ним, то есть от , , и . Тогда для проверки корректности переходов требуется перебрать все четверки символов , , и из таблицы и проверить, что из них возможно получить символ . Если четверка символов выходит за границу таблицы, то указывается меньшее количество позиций. .
отвечает за то, что в каждой ячейке находится ровно один символ. .
Мы построили функцию сведения
. Покажем, что выполнима тогда и только тогда, когда .1) Пусть
, тогда существует цепочка переходов , где в присутствует допускающее состояние , следовательно можем построить таблицу, аналогичную приведенной выше, а значит можем построить выполнимую формулу .2) Пусть в результате работы функции
получили выполнимую формулу , следовательно существует такой набор переменных , что на нем принимает значение . Тогда можем по данному набору построить непротиворечивую таблицу, по которой можно восстановить цепочку переходов . Совершив эти переходы машина перейдет в допускающее состояние за время , следовательно .Значит,
и из доказанного ранее следует,что .Теорема доказана.