# Understanding the complexity class $P^O$ for randomized oracles

We know from Toda's theorem that $PH \subseteq P^{PP}$. What do we know about the following classes?

$$P^{ZPP}, P^{RP}, \text{ and } P^{BPP}$$

$\let\mr\mathrm \mr{BPP}$ is in the second level of polynomial hierarchy by the Gács–Sipser–Lautemann theorem, and it is an easy exercise to show that $$\mr{P^{ZPP}}=\mr{ZPP}\subseteq\mr{P^{RP}}\subseteq\mr{P^{BPP}}=\mr{BPP}.$$ The least trivial of these is the inclusion $\mr{P^{BPP}}\subseteq\mr{BPP}$: let $L_0$ be a language decidable by a machine $M_0$ running in time $n^c$ with an oracle for a language $L_1\in\mr{BPP}$. By standard amplification, $L_1$ is computable by a randomized poly-time machine $M_1$ with error bounded by (say) $2^{-n}$. So, if we take $M_0$, and replace the oracle with $M_1$ as a subroutine, we obtain a randomized poly-time machine for $L_0$ with error bounded by $n^c2^{-n}<1/3$.
$\mr{P^{RP}}$ contains $\mr{RP}\cup\mr{coRP}$, hence it equals $\mr{RP}$ only if $\mr{RP}=\mr{coRP}=\mr{ZPP}$. This is not known to be true, nevertheless all the classes mentioned above are conjectured to coincide with $\mr P$, and there are conditional results to that effect.
• Please clarify this point: $M^O$ is a deterministic machine if $M$ is a deterministic machine. So, shouldn't $P^{BPP}$ be a deterministic complexity class? Nov 30 '14 at 17:12
• No, it doesn’t work that way. Any $\mr{BPP}$ language $O$ is trivially decidable by a deterministic machine with oracle $O$, which just passes the input to the oracle and returns the answer provided by the oracle. Determinism of oracle machine has nothing to do with determinism of unrelativized machines computing the same language. Nov 30 '14 at 17:19
• I believe $M$ cannot simply return the answer of the $BPP$ oracle. For the oracle, it is acceptable if it decides the language membership with probability better than (say) 2/3. However, the deterministic machine $M$ should "perfectly" decide the membership: It should output 1 if and only if the input belongs to some language. Nov 30 '14 at 17:25