| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
| proof =
'''Существование оракула <tex>A</tex>.'''
Покажем существование такого оракула Рассмотрим [[PS-полнота языка верных булевых формул с кванторами (TQBF) | PS-полный язык <tex>A\mathrm{TQBF}</tex>, что ]]. <tex>\mathrm{P^A{TQBF}} = \overset{(1)}{\subseteq}\mathrm{NP^A{TQBF}} \overset{(2)}{\subseteq} </tex>. Рассмотрим язык <tex> \mathrm{NPS^{TQBF} } \overset{(3)}{= }\mathrm{ PS^{TQBF}} \Phi | \Phi</tex> — булева формула с кванторами <tex>, \Phi overset{(4)}{= 1}\mathrm{PS}</tex>. [[PS-полнота языка верных булевых формул с кванторами \overset{(TQBF5) | <tex> }{\subseteq}\mathrm{P^{TQBF} }\Rightarrow</tex> является <br/><tex>PS\Rightarrow \mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>-полным языком]].*# <tex> \mathrm{P} \subset subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subset subseteq \mathrm{NP^{TQBF}} </tex>.* # <tex>T(p,x) \ge S(p, x)</tex>, для любых <tex>p, x \Rightarrow \mathrm{NP^{TQBF}} \subset 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{PSPSC}</tex>-полный <tex>\Rightarrow \mathrm{PS} \in subseteq \mathrm{P^{TQBF}}</tex>.Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>.
----
'''Существование оракула <tex>B</tex>.'''
Покажем существование такого оракула <tex>B</tex>, что <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>. Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n | \exists x</tex>, что <tex>|x| = n\}</tex>. Ясно, что <tex>\forall B: U_B \in \mathrm{NP^B}</tex> (легко написать программу, проверяющую сертификат). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P^B}</tex>.
