211
правок
Изменения
м
Нет описания правки
Если <tex>w \in L</tex>, то существует путь из стартовой конфигурации в финишную, причём длины не более, чем <tex>2^{O(p(n))}</tex>, а значит формула <tex>\phi</tex> верна.
Если формула <tex>f(M, w)</tex> оказалась верна, то существует путь из стартовой конфигурации в финишную длины не более, чем <tex>2^{O(p(n))}</tex>. Значит, ДМТ <tex>M</tex> допускает слово <tex>w</tex>. Тогда <tex>w \in L</tex>.
Таким образом, <tex>TQBF \in \mathrm{PSH}</tex>.
