11
правок
Изменения
→Доказательство того, что SAT ∈ NPH
# <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: \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^32)</tex>.
Покажем, что <tex>\phi</tex> выполнима тогда и только тогда, когда <tex>\langle m, x, 1^t \rangle \in BH_{1N}</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>\langle m, x, 1^t\rangle \in BH_{1N}</tex>.
Значит, <tex>SAT \in NPH</tex> и из доказанного ранее следует,что <tex>SAT \in NPC</tex>.
Теорема доказана.
