0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy