Теорема Бейкера-Гилла-Соловэя
Версия от 10:58, 16 июня 2010; Diniska (обсуждение | вклад)
Формулировка
оракулы и такие что
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]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]
