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

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

[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]PS[/math]-полный язык (разрешимый на полиномиальной памяти) [math]NP^A=NPS=PS=P^A[/math]

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