211
правок
Изменения
м
Нет описания правки
<tex>TQBF=\{Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}</tex>
}}
Чтобы доказать, что <tex>TQBF \in PSPACE-complete\mathrm{PSC}</tex>, необходимо показать, что эта задача принадлежит <tex>PSPACETQBF \in \mathrm{PSH}</tex> и что она <tex>PSPACETQBF \in \mathrm{PS}</tex>-трудная.
{{Лемма
|about=1
|statement=<tex>TQBF \in PSPASE\mathrm{PS}</tex>
|proof=Чтобы доказать это, просто приведём программу <tex>solve</tex>, решающую булеву формулу с кванторами на <tex>O(n)</tex> дополнительной памяти и работающую за конечное время.
<tex>solve(Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \phi(x_1, x_2, \dots, x_n))</tex>
{{Лемма
|about=2
|statement=<tex> \forall L TQBF \in PS , L \leq_p TQBFmathrm{PSH}</tex>.|proof=Рассмотрим какой-то язык <tex>L \in PSPACE\mathrm{PS}</tex>.
Построим функцию <tex>f \colon \forall x \in L \Leftrightarrow f(x) \in TQBF</tex>.
Так как <tex>L \in PSPACE\mathrm{PS}</tex>, то существует какая-то детерминированная машина Тьюринга <tex>M</tex>, которая его распознаёт за полиномиальное от размера входа время.
Пусть <tex>I</tex> — мгновенное описание <tex>M</tex>, тогда выражение <tex>\exists I</tex> обозначает <tex> (\exists x_1) (\exists x_2)\cdots(\exists x_n)</tex>, где <tex>\{x_i\}</tex> — все переменные мгновенного описания <tex>M</tex>. Аналогично выражение <tex> \forall I</tex> обозначает <tex> (\forall x_1) (\forall x_2)\dots(\forall x_n)</tex>. Теперь рассмотрим два мгновенных описание <tex>M: A</tex> и <tex>B</tex>. Напишем рекурсивную функцию <tex>\phi(A, B, t)</tex>, которая будет переводить утверждение <tex>A\vdash^tB</tex> в TQBF за полиномиальное относительно длины входа время.
Если <tex>w \not\in L</tex>, то если мы зададим корректное стартовое состояние, то пути до корректного финишного состояния существовать не может.
Таким образом, <tex>TQBF \in \mathrm{PSH}</tex>.
}}
[[Категория: Теория сложности]]
