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