68
правок
Изменения
Нет описания правки
<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</tex> необходимо показать , что:эта задача принадлежит <tex>PSPACE</tex> и что она <tex>PSPACE</tex>-трудная.
{{Лемма
|about=1
