12
$\begingroup$

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?

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

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.

$\endgroup$

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.