Изменения
Нет описания правки
* Покажем существование такого оракула <tex>B</tex>, что <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
Пусть <tex>B\--</tex> произвольное множество, а <tex>U_B = \{1^n | \exists x</tex>, что <tex>|x| = n\}</tex>.
Ясно, что <tex>\forall B : U_B \in \mathrm{NP^B}</tex> (легко написать программу, проверяющую сертификат). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P^B}</tex>.
}}
