Изменения

Докажем, что эта проблема [[NP-полнота|<tex>NP\,\!</tex>-полна.]]

*<tex>SAT \in </tex> [[NP|<tex>NP</tex>]]*<tex>SAT \in </tex> [[NP-полнота|<tex>NPH</tex>]]

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

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

Если же у нас существует такой сертификат <tex>y\,\!</tex>, на котором верификатор выдаёт единицу, то, значит, и формула является удовлетворимой.

Теперь докажем, что <tex>SAT \in NPH.</tex> Для этого сведём проблему [[NP-полнота_задачи_BH1N|<tex>BH_{1N}\,\!</tex>]], которая, как нам известно, <tex>NP\,\!</tex>-полна, к проблеме <tex>SAT.\,\!</tex> Тогда получится, что любая проблема из <tex>NP\,\!</tex> может быть сведена по Карпу к проблеме <tex>BH_{1N}\,\!</tex>, и, по транзитивности сведения по Карпу, к <tex>SAT.\,\!</tex>

По условию проблемы <tex>BH_{1N}\,\!</tex>, у нас есть недетерминированная машина Тьюринга <tex>m\,\!</tex>, причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы, входное слово <tex>x\,\!</tex> и время <tex>t\,\!</tex>, заданное в унарной системе счисления. Нам же надо построить такую булеву формулу <tex>\phi\,\!</tex>, что она выполнима тогда, и только тогда, когда <tex>m\,\!</tex>, получив на вход <tex>x\,\!</tex>, делает не более <tex>t\,\!</tex> шагов и допускает это слово.

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

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

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

|+ '''Процесс работы машины <tex>m\,\!</tex> на входе <tex>x\,\!</tex>'''

! style="border-right:3px solid gray;" | <tex>q_0\,\!</tex>| <tex>q_{0, 0}\,\!</tex> || <tex>q_{0, 1}\,\!</tex> || || || || || || || <tex>q_{0, t}\,\!</tex>

! style="border-right:3px solid gray;" | <tex>q_1\,\!</tex>| <tex>q_{1, 0}\,\!</tex> || <tex>q_{1, 1}\,\!</tex> || || || || || || || <tex>q_{1, t}\,\!</tex>

! style="border-right:3px solid gray;" | <tex>q_i\,\!</tex>| || || || <tex>q_{i, j - 1}\,\!</tex> || <tex>q_{i, j}\,\!</tex> || <tex>q_{i, j + 1\,\!}</tex> || <tex>q_{i, j + 2\,\!}</tex> || ||

! style="border-right:3px solid gray;" | <tex>q_{i + 1}\,\!</tex>| || || || <tex>q_{i, j - 1}\,\!</tex> || <tex>q_{i, j}\,\!</tex> || <tex>q_{i, j + 1\,\!}</tex> || || ||

! style="border-right:3px solid gray;" | <tex>q_t\,\!</tex>| <tex>q_{t, 0}\,\!</tex> || <tex>q_{t, 1}\,\!</tex> || || || || || || || <tex>q_{t, t}\,\!</tex>

Каждый элемент таблицы <tex>q_{i, j}\in \Sigma \cup Q</tex>. И для каждого такого элемента заведём <tex>|\Sigma| + |Q|\,\!</tex> переменных <tex>Y_{i, j, c} = [q_{i, j} = c]\ \forall c \in \Sigma \cup Q\,\!</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>m</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-1,c_1^`} \lor Y_{i,j-1,c_2^`} \lor \ldots \lor Y_{i,j-1,c_{|\Sigma|-1}^`})) \land (Y_{i,j,c_1^`} \lor Y_{i,j,c_2^`} \lor \ldots \lor Y_{i,j,c_{|\Sigma|-1}^`})) \land (Y_{i,j+1,c_1^`} \lor Y_{i,j+1,c_2^`} \lor \ldots \lor Y_{i,j+1,c_{|\Sigma|-1}^`})))</tex>.