<p>Clearly, $\mathrm{RPH}\subseteq\mathrm{BPP}$. On the other hand, $\mathrm{BPP}=\mathrm{ZPP^{promiseRP}}$ (<a href="http://dx.doi.org/10.1007/3-540-49116-3_9">Buhrman&amp;Fortnow</a>, <a href="http://people.cs.uchicago.edu/~fortnow/papers/rpvsbpp.pdf">pdf</a>), 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.</p>

CC BY-SA 3.0
2015-08-28T09:20:23.533Z
2015-08-28T12:05:17.927Z
2015-08-28T12:05:17.927Z
Emil Jeřábek
<p>I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., <a href="https://en.wikipedia.org/wiki/Polynomial_hierarchy">here</a>), the role of $NP$ would be replaced by $RP$? </p>

<p>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$). </p>

<p>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$. </p>

<p>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.</p>

<p>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.</p>

<p>Is anything known about this?</p>

CC BY-SA 3.0
2015-08-28T00:12:14.833Z
What does it mean exactly to have RP as an oracle, e.g. $P^{RP}$?
usul
<cc.complexity-theory><randomized-algorithms><randomness>
Randomized Polynomial Hierarchy?
Andras Farago
# Randomized Polynomial Hierarchy?

(Asked by: username_0 on 2015-08-27)

I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., [here](https://en.wikipedia.org/wiki/Polynomial_hierarchy)), 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?

**Tags:** cc.complexity-theory, randomized-algorithms, randomness
> **Comments:**
> **username_1**: What does it mean exactly to have RP as an oracle, e.g. $P^{RP}$?  

---

## 1 answers

### Answer by username_2 on 2015-08-28. Score: 8

Clearly, $\mathrm{RPH}\subseteq\mathrm{BPP}$. On the other hand, $\mathrm{BPP}=\mathrm{ZPP^{promiseRP}}$ ([Buhrman&Fortnow](http://dx.doi.org/10.1007/3-540-49116-3_9), [pdf](http://people.cs.uchicago.edu/~fortnow/papers/rpvsbpp.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.


---

