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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Формулировка == <tex>\exists{}</tex> оракулы <tex>A</tex> и <tex>B</tex> такие что <tex>P^A=NP^A</tex> <tex>P^B\ne{}NP^B</tex> 1) <te…»)
 
м
Строка 7: Строка 7:
 
1) <tex>A</tex> - <tex>PS</tex>-полный язык (разрешимый на полиномиальной памяти)
 
1) <tex>A</tex> - <tex>PS</tex>-полный язык (разрешимый на полиномиальной памяти)
 
<tex>NP^A=NPS=PS=P^A</tex>
 
<tex>NP^A=NPS=PS=P^A</tex>
 +
 
2) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex>
 
2) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex>

Версия 10:58, 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]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]