All Questions
1 question
12
votes
1
answer
491
views
Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$
Complexity Zoology by Greg Kuperberg states that there is a language $X$ such that $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X$ — in other words, $\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\...
- 16.6k