68
правок
Изменения
Нет описания правки
{{Лемма
|about=2
|statement=<tex> \forall L \in PS \Rightarrow , L \leq_p TQBF</tex>
|proof=Рассмотрим какой-то язык <tex>L \in PSPACE</tex>. Построим функцию <tex>f : \forall x \in L \Leftrightarrow f(x) \in TQBF</tex>
Так как <tex>L \in PSPACE</tex>, то существует какая-то детерминированная машина Тьюринга <tex>M</tex>, которая его распознаёт за полиномиальное время на ленте полиномиального размера.
