# $\mathrm{\oplus P^{BPP}\subseteq BPP^{\oplus P}}$

Toda showed long ago that $$\mathrm{PH\subseteq BP.\oplus P\subseteq BPP^{\oplus P}}$$. That somehow describes the power of Parity Non-deterministic Computation.

If we swap the base and the exponent of the relativized class $$\mathrm{BPP^{\oplus P}}$$ to obtain yet another relativized one, namely $$\mathrm{\oplus P^{BPP}}$$. Then what have we obtained? A bigger or a smaller class?

You get a smaller one, in words $$\mathrm{{\oplus P}^{BPP}\subseteq BPP^{\oplus P}}$$. Indeed, the stronger claim that $$\mathrm{{\oplus P}^{BPP}\subseteq BPP^{\oplus P[1]}}$$ also holds.

Consider a language $$L\in \mathrm{{\oplus P}^{BPP}}$$, by definition, there exists an oracular non-deterministic machine $$N$$ and a $$\mathrm{BPP}$$ machine $$M$$ such that: on a given input string $$x\in \Sigma^*$$, we have that $$x\in L$$ if and only if $$N^M(x)$$ has an odd number of accepting paths.

Now, we may assume that by repetition and taking majority, the probability of $$M$$ to produce wrong answer is exponentially small.

The following language $$\mathcal{O}$$ is in $$\oplus P$$: on an input string $$x\in\Sigma^*$$ and a polynomially long random bit string $$r$$ (i.e. input data is $$(x,r)$$), simulate $$N^M(x)$$ where the random coin tosses using inside the oracle calls to $$M$$ are taken from $$r$$ one by one from left to right; accept only when the number of accepting paths is odd.

So, on a given input string $$x\in\Sigma^*$$, we guess a polynomially long random bit string $$r$$, call the oracle $$L\in\oplus\mathrm{P}$$ on input $$(x, r)$$and return the same answer.

Clearly, the probability that the random bit string $$r$$ makes $$M$$ produce wrong answer to any oracle call is extremely small. So, w.h.p the answer returned by the only one call to $$\mathcal{O}$$ is identical to the answer of $$N^M(x)$$.

Thus, $$L\in\mathrm{BPP^{\oplus P[1]}}$$. The claim that we obtain a smaller class holds.