Теорема Бейкера-Гилла-Соловэя — различия между версиями

Версия 11:43, 16 июня 2010

[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]:

@@ Строка 5: / Строка 5: @@
 <tex>P^B\ne{}NP^B</tex>
-) <tex>A</tex> - <tex>PS</tex>-полный язык (разрешимый на полиномиальной памяти)
+)<tex>A</tex>=<tex>TQBF</tex>
-<tex>NP^A=NPS=PS=P^A</tex>
+ <tex>NP^{TQBF}\subset{NPS^{TGBF}}=PS^{TQBF}=PS\subset{P^{TQBF}\subset{NP^{TQBF}}}</tex>
 ) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex>