1
$\begingroup$

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} $$

$\endgroup$
0
3
+50
$\begingroup$

$\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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ Nov 30 '14 at 17:12
  • $\begingroup$ 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. $\endgroup$ Nov 30 '14 at 17:19
  • $\begingroup$ 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. $\endgroup$ Nov 30 '14 at 17:25
  • 3
    $\begingroup$ I think you don’t understand what an oracle machine is. The oracle does not run any algorithms, BPP or otherwise. The oracle is a lady in a fancy dress who mumbles a few magic words, stares in a crystal ball, and tells you the answer. It is always correct, and it does not involve any probability. $\endgroup$ Nov 30 '14 at 17:49
  • $\begingroup$ Oh, I see. Thanks for the magical explanation, it's now crystal clear :) $\endgroup$ Nov 30 '14 at 17:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.