211
правок
Изменения
м
Чтобы доказать, что <tex>TQBF \in \mathrm{PSC}</tex>, необходимо показать, что <tex>TQBF \in \mathrm{PSH}</tex> и <tex>TQBF \in \mathrm{PS}</tex>.
Нет описания правки
}}
{{Лемма
|about=1
Докажем, что сведение <tex>f</tex> корректно.
Если <tex>w \in L</tex>, то существует путь из стартовой конфигурации в финишную, причём длины не более, чем <tex>2^{\Omega n}</tex>, а значит формула <tex>\phif(M, w)</tex> верна.
Если формула <tex>f(M, w)</tex> оказалась верна, то существует путь из стартовой конфигурации в финишную длины не более, чем <tex>2^{\Omega n}</tex>. Значит, ДМТ <tex>M</tex> допускает слово <tex>w</tex>. Тогда <tex>w \in L</tex>.
Таким образом, <tex>TQBF \in \mathrm{PSH}</tex>.
}}
{{Теорема
|statement=<tex>TQBF \in \mathrm{PSC}</tex>.
|proof=Доказательство непосредственно следует из лемм.
}}
[[Категория: Теория сложности]]
