11
правок
Изменения
→Доказательство: часть 2
<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>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>.
Теорема доказана.
