Теорема Бейкера-Гилла-Соловэя

Формулировка

[math]\exists{}[/math] оракулы [math]A[/math] и [math]B[/math] такие что

[math]P^A=NP^A[/math] [math]P^B\ne{}NP^B[/math]

1)[math]A[/math]=[math]TQBF[/math]

[math]NP^{TQBF}\subset{NPS^{TQBF}}=PS^{TQBF}=PS\subset{P^{TQBF}\subset{NP^{TQBF}}}[/math]

2) [math]B[/math]:[math]L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}[/math]