Теорема Бейкера-Гилла-Соловэя
Формулировка
оракулы и такие что
1)=
2) :
[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^{TGBF}}=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]
