Изменения
Нет описания правки
# <tex> \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} </tex>.
# Так как <tex>S(p,x) \le T(p, x)</tex>, то<tex> \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} </tex>.
# По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>.
# <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex>.
# <tex> \mathrm{TQBF} \in \mathrm{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} </tex>.
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>
----
