Изменения

|definition=<tex>Quantified Boolean Formula</tex> — это пропозициональная формула с кванторами. Кванторы для каждой переменной записываются в начале выражения.

<tex>solve(Q_k x_k Q_1 x_1 \ldots Q_n x_n \phi(x_1, x_2, \ldots, x_n))</tex> '''if''' <tex>k n == n</tex>0 '''return''' <tex>\phi(x_1, x_2, \ldots, x_n)</tex> '''if''' <tex>Q_k Q_1 = \forall</tex> '''return''' <tex>solve(Q_{k+12} x_{k+12} \ldots Q_n x_n \phi(0, x_{k+12}, \ldots, x_n)) \land solve(Q_{k+12} x_{k+12} \ldots Q_n x_n \phi(1, x_{k+12}, \ldots, x_n))</tex> '''if''' <tex>Q_k Q_1 = \exists</tex> '''return''' <tex>solve(Q_{k+12} x_{k+12} \ldots Q_n x_n \phi(0, x_{k+12}, \ldots, x_n)) \lor solve(Q_{k+12} x_{k+12} \dots Q_n x_n \phi(1, x_{k+12}, \ldots, x_n))</tex>

Пусть <tex>\Omega w = |\Sigma \cup Q|</tex>, <tex>I</tex> — конфигурация <tex>M</tex>. Конфигурация однозначно задаётся позицией и содержанием рабочей ленты. Введём обозначение <tex>x_{I,i,c}</tex> — в конфигурации <tex>I</tex> на <tex>i</tex>-том месте стоит символ <tex>c</tex>. Тогда размер конфигурации равен <tex>\Omega w r(n)</tex>. Следовательно всего конфигураций <tex>2^{\Omega w r(n)}</tex>.

Под выражением <tex>\exists I</tex> будем понимать <tex> \exists x_{I,1,c_1} \, \exists x_{I,1,c_2} \ldots \exists x_{I,1,c_\Omegac_w} \, \exists x_{I,2,c_1} \ldots</tex> Аналогично выражение <tex> \forall I</tex> обозначает <tex> \forall x_{I,1,c_1} \, \forall x_{I,1,c_2} \ldots \forall x_{I,1,c_\Omegac_w} \, \forall x_{I,2,c_1} \ldots</tex>

Общую длину получившейся формулы можно представить как <tex>L(t) = 2 L(t-1)+const</tex>. Заметим, что данная формула имеет из-за умножения на 2 на каждом шаге рекурсии <tex>L(t)</tex> будет иметь экспоненциальный размеротносительно <tex>t</tex>. Нас это не устраивает, поэтому так как нам необходимо полиномиальное сведение. Поэтому воспользуемся квантором <tex>\forall</tex> и перепишем её следующим образом:

<tex>\phi(A, B, t) = \exists R \,\forall U \,\forall V \, \{\phi(U, V, t-1) \lor [\neg(U = A \land V = R) \land \neglor (U = R \land V = B)]\rightarrow \phi(U, V, t-1)\}</tex>.

Размер Получившаяся формула верна, если существует такая промежуточная конфигурация <tex>R</tex>, что для любых конфигураций <tex>U</tex> и <tex>V</tex> из того, что эти конфигурации нам интересны следует, что верно <tex>\phi(U, V, t-1)</tex>. А значит, конфигурация <tex>B</tex> достижима из конфигурации <tex>A</tex> не более, чем за <tex>2^t</tex> шагов. За один шаг рекурсии длина максимального пути между конфигурациями уменьшается в два раза. Поэтому общую длину получившейся формулы можно представить как <tex>L(t) = L(t-1)+const</tex>, где <tex>const = \|\exists R \,\forall U \,\forall V \, \{\| + \|\land [(U = A \land V = R) \lor (U = R \land V = B)]\}\|</tex>.Следовательно, размер полученной функции <tex>\phi(A, B, t)</tex> полиномиален относительно <tex>nt</tex>.

<tex>f(M, w) = \exists S \, \exists F \, (S - start) \land (F - accept) \land \phi(S, F, log_2(2^{\Omega w r(n)})))</tex>.

<tex>F - accept = x_{SF, |w| + 1, \#_y} \lor \ldots \lor x_{SF, r(n), \#_y}</tex>.

Если <tex>w \in L</tex>, то существует путь из стартовой конфигурации в финишную, причём длины не более, чем <tex>2^{\Omega w r(n)}</tex>, а значит формула <tex>f(M, w)</tex> верна.

Если формула <tex>f(M, w)</tex> оказалась верна, то существует путь из стартовой конфигурации в финишную длины не более, чем <tex>2^{\Omega w r(n)}</tex>. Значит, ДМТ <tex>M</tex> допускает слово <tex>w</tex>. Тогда <tex>w \in L</tex>.