1
Wyrocznia, względem której
Zoologia złożoności autorstwa Grega Kuperberga stwierdza, że istnieje język XXX taki, że BPPX⊈Δ2PXBPPX⊈Δ2PX\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X - innymi słowy, BPPX⊈PNPXBPPX⊈PNPX\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\mathsf{NP}^X} - ale nie podaje odniesienia do tego wyniku. Dlaczego tak się dzieje? Lub gdzie można znaleźć dowód? To pytanie jest częściowo uzasadnione moją odpowiedzią na pytanie „Co wiadomo …