I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., here), the role of $NP$ would be replaced by $RP$?

It seems, we could still build a hierarchy, the same way as $PH$ is built, just using $RP$ everywhere instead of $NP$, and $coRP$ instead of $coNP$. Let us call it Randomized Polynomial Hierarchy ($RPH$).

My first guess is that $RPH\subseteq BPP$, or maybe $RPH=BPP$. It is based on the known fact that $NP=RP$ implies $PH=BPP$. Nevertheless, if $P\neq RP$, then $RPH$ could still be a proper, infinite hierarchy within $BPP$.

Of course, the edge of the issue is blunted by the fact that $P=RP$ is conjectured (even $P=BPP$), which would flatten $RPH$ into $P$. However, $P=RP$ is not known at this time, and it has resisted all proof attempts so far. Therefore, $RPH$ still has at least some chance to be a proper hierarchy.

While $RPH$, admittedly, has a good chance to be "flat," could the concept still be useful for something nontrivial? Here is an example: if one can prove $RPH=BPP$, then it would yield that $P=RP$ implies $P=BPP$, which, I think, would be an interesting result.

Is anything known about this?

  • 2
    $\begingroup$ What does it mean exactly to have RP as an oracle, e.g. $P^{RP}$? $\endgroup$
    – usul
    Aug 28, 2015 at 0:12
  • 2
    $\begingroup$ @usul : $\:$ cs.stackexchange.com/a/26332/12859 $\;\;\;\;$ $\endgroup$
    – user6973
    Aug 28, 2015 at 1:40

1 Answer 1


Clearly, $\mathrm{RPH}\subseteq\mathrm{BPP}$. On the other hand, $\mathrm{BPP}=\mathrm{ZPP^{promiseRP}}$ (Buhrman&Fortnow, pdf), so the only way the hierarchy didn’t collapse to (at most) the second level and didn’t exhaust $\mathrm{BPP}$ would be for the unlikely reason that $\mathrm{RP}$ oracles were significantly weaker than $\mathrm{promiseRP}$ oracles.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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