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