Изменения

|definition=<tex>\mathrm{TQBF}</tex> расшифровывается как '''True Quantified Boolean Formula'''. Это язык верных булевых формул с кванторами.<br/><tex>\mathrm{TQBF}=\{Q_1 x_1 Q_2 x_2 \cdots ldots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}</tex>.}}{{Определение|definition=<tex>Quantified Boolean Formula</tex> — это пропозициональная формула с кванторами. Кванторы для каждой переменной записываются в начале выражения.

|statement=<tex>\mathrm{TQBF } \in PSPACSE\mathrm{PS}</tex>.|proof=Чтобы доказать это, просто приведём программу<tex>solve</tex>, которая требует решающую булеву формулу с кванторами на <tex>O(n)</tex> дополнительной памяти и работает работающую за конечное время. <tex>solve(Q_1 x_1 Q_2 x_2 \cdots ldots Q_n x_n \phi(x_1, x_2, \dotsldots, x_n))</tex> '''if''' n == 0 '''return''' <tex>\phi</tex> '''if''' <tex>Q_1 == \forall</tex> '''return''' <tex>solve(Q_2 x_2 Q_{2} x_{2} \cdots ldots Q_n x_n \phi(0, x_2x_{2}, \dotsldots, x_n)) \land solve(Q_2 x_2 Q_{2} x_{2} \cdots ldots Q_n x_n \phi(1, x_2x_{2}, \dotsldots, x_n))</tex> '''if''' <tex>Q_1 == \exists</tex> '''return''' <tex>solve(Q_2 x_2 Q_{2} x_{2} \cdots ldots Q_n x_n \phi(0, x_2x_{2}, \dotsldots, x_n)) \lor solve(Q_2 x_2 Q_{2} x_{2} \cdots dots Q_n x_n \phi(1, x_2x_{2}, \dotsldots, x_n))</tex>Эта программа требует <tex>O(n)</tex> дополнительной памяти для хранения стека рекурсивных вызовов. Максимальная глубина стека — <tex>n</tex>.

|statement=<tex> \forall L mathrm{TQBF} \in PS , L \leq_p TQBFmathrm{PSH}</tex>.|proof=Рассмотрим какой-то язык <tex>L \in PSPACE\mathrm{PS}</tex>. Построим такую функцию <tex>f \colon \forall </tex>, что <tex>x \in L \Leftrightarrow f(x) \in \mathrm{TQBF}</tex> и <tex>T(f, x) \le p(|x|)</tex>, где <tex>p</tex>— полином. Так как <tex>L \in PSPACE\mathrm{PS}</tex>, то существует какая-то детерминированная машина Тьюринга <tex>M</tex>, которая распознающая его распознаёт за полиномиальное от с использованием памяти полиномиального размера . Будем считать, что длина ленты машины <tex>M</tex> есть <tex>r(n)</tex>, где <tex>r</tex> — полином, а <tex>n</tex> — длина входа время. Пусть <tex>w = |\Sigma \cup Q|</tex>, <tex>I</tex> — мгновенное описание конфигурация <tex>M</tex>. Конфигурация задаётся позицией и содержанием рабочей ленты. Введём обозначение <tex>x_{I,i, тогда выражение c}</tex> — в конфигурации <tex>\exists I</tex> обозначает на <tex>i</tex>-том месте стоит символ <tex>c</tex>. Тогда размер конфигурации равен <tex> w r(\exists x_1n) </tex>. Следовательно всего конфигураций <tex>2^{w r(\exists x_2)\cdots(\exists x_nn)}</tex>, где . Под выражением <tex>\{x_i\}exists I</tex> — все переменные мгновенного описания будем понимать <tex>M\exists x_{I,1,c_1} \, \exists x_{I,1,c_2} \ldots \exists x_{I,1,c_w} \, \exists x_{I,2,c_1} \ldots</tex>. Аналогично выражение <tex> \forall I</tex> обозначает <tex> (\forall x_1) (x_{I,1,c_1} \, \forall x_{I,1,c_2} \ldots \forall x_2)x_{I,1,c_w} \dots(, \forall x_n)x_{I,2,c_1} \ldots</tex>. Теперь рассмотрим два мгновенных описание  Рассмотрим функцию <tex>M: \phi(A, B, t)</tex> и , проверяющую следующее условие: конфигурация <tex>B</tex>. Напишем рекурсивную функцию достижима из конфигурации <tex>\phi(A</tex> не более, B, чем за <tex>2^t)</tex>, которая будет переводить утверждение шагов. <tex>\phi(A, B, 0) = (A = B) \lor (A\vdash^tBB)</tex> в TQBF за полиномиальное относительно длины входа время.

<tex>\phi(A, B, t) = \\ (\exists R) (\forall U) (\forall V) \ \{\phi(U, V, t/2) \lor [\negphi(A = U \land R = V) \land \neg(R = U \land B = V)]\}</tex> :Переменые <tex> U </tex> и <tex>V</tex> важно рассмотреть только в двух случаях: когда первое из них стартовое, второе — промежуточное, или первое — промежуточное, а второе — финишное. Поэтому для всех остальных вариантов выражение <tex>[\neg(A = U \land R = V) \land \neg(R = U \land B = V)]</tex> будет истинно. Если <tex>A = U \land R = V</tex> то, чтобы <tex>\phi(A, B, t-1)</tex> было истинно, необходимо наличие такого мгновенного описания <tex>R</tex>, чтобы было выполненно утверждение: <tex>A\vdash^{t/2}R</tex>. Если <tex>R = U \land B = V</tex> то, нас интересует мгновенное описание <tex>R</tex> такое, что <tex>R\vdash^{t/2}B</tex>.Заметим, что размер функции <tex>\phi(aR, B, t)</tex> равен размеру <tex>\phi(A, B, t/2)</tex> с константной добавкой <tex>(\exists R) (\forall U) (\forall V) \ \{\ * \lor [\neg(A = U \land B = R) \land \neg(A = R \land B = V-1)]\}</tex> .Теперь мы можем записать функцию <tex>f(M, w)</tex>, которая будет переводить ДМТ <tex>M</tex> и слово на ленте <tex>w</tex> в <tex>TQBF</tex>.

Общую длину получившейся формулы можно представить как <tex>fL(M, wt) = 2 L(\exists I_st-1) (\exists I_f) (x_{I_s+const</tex>. Заметим, 0} = start \land x_{I_s, 1} = w[1] \land \dots \land x_{I_s, |w|} = w[|w|]) \land что из-за умножения на 2 на каждом шаге рекурсии <tex>L((\exists it) x_{I_f</tex> будет иметь экспоненциальный размер относительно <tex>t</tex>. Нас это не устраивает, i} = finish) так как нам необходимо полиномиальное сведение. Поэтому воспользуемся квантором <tex>\land \phi(Start, Finish, 2^{log_2(c^{1+p(n)}})forall</tex>и перепишем её следующим образом:

Докажем, что получившаяся булева формула с кванторами удовлетворима тогда и только тогда, когда <tex>w \in Lphi(A, B, t) = \exists R \,\forall U \,\forall V \, \{[(U = A \land V = R) \lor (U = R \land V = B)] \rightarrow \phi(U, V, t-1)\}</tex>.

Если Получившаяся формула верна, если существует такая промежуточная конфигурация <tex>w \in LR</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>t</tex>. Теперь мы можем записать функцию <tex>f(M, w)</tex>, которая будет переводить ДМТ <tex>M</tex> и слово на ленте <tex>w</tex> в формулу из <tex>\mathrm{TQBF}</tex>. <tex>f(M, w) = \exists S \, \exists F \, (S - start) \land (F - accept) \land \phi(S, F, log_2(2^{w r(n)})))</tex>. Выражения <tex>S - start</tex> и <tex>F - accept</tex> можно записать следующим образом: <tex>S - start = x_{S, 1, w[1]} \land x_{S, 2, w[2]} \land \ldots \land x_{S, |w|, w[|w|]} \land x_{S, |w| + 1, B} \ldots \land x_{S, r(n) , B}</tex>. <tex>F - accept = x_{F, 1, \#_y} \lor \ldots \lor x_{F, r(n), \#_y}</tex>.  Докажем, что сведение <tex>f</tex> корректно. Если <tex>w \not\in L</tex>, то если мы зададим корректное стартовое состояниесуществует путь из стартовой конфигурации в финишную, длины не более, чем <tex>2^{w r(n)}</tex>, а значит формула <tex>f(M, w)</tex> верна. Если формула <tex>f(M, w)</tex> оказалась верна, то пути до корректного финишного состояния существовать существует путь из стартовой конфигурации в финишную длины не можетболее, чем <tex>2^{w r(n)}</tex>. Значит, ДМТ <tex>M</tex> допускает слово <tex>w</tex>. Тогда <tex>w \in L</tex>. Таким образом, <tex>\mathrm{TQBF} \in \mathrm{PSH}</tex>.}} {{Теорема|statement=<tex>\mathrm{TQBF} \in \mathrm{PSC}</tex>.|proof=Доказательство непосредственно следует из лемм.