<p>I have the following thoughts so I'd like to hear are there any straightforward implications which might support or undermine them.</p>

<p>You have a class BPP where problems have a TM with bounded two side error and constant ratio of correct leaves in your computational tree.</p>

<p>You have a class NP, which you can think of there is a TM with computational tree which is correct for no instances , but for yes instance $x$ you can have the correct leaves ration as small as $\frac{1}{2^{p(|x|)}}$.</p>

<p>If you kind of combine this you get for no instances all leaves correct for yes instances only the constant ratio, and this is class RP. </p>

<p>So the conjecture is $RP = NP \cap BPP$. What are the important implications? Is there a 1-line proof?</p>

<p>From me, I can add that the widely believed conjecture $BPP = P$ definitely supports the claim.</p>

<p>Thank you. </p>

CC BY-SA 3.0
2016-12-05T12:31:46.833Z
I don't think this conjecture is known. It certainly doesn't have any one line proof.
Yuval Filmus
CC BY-SA 3.0
2016-12-06T13:08:03.150Z
This is not known. However, it is known (and fairly easy) that $\mathrm{NP\subseteq BPP}$ implies $\mathrm{NP=RP}$. I have a déjà-vu feeling that this was already discussed somewhere on this site.
Emil Jeřábek
<complexity-classes>
The relation between RP, BPP and NP
Eugene
# The relation between RP, BPP and NP

(Asked by: username_0 on 2016-12-05)

I have the following thoughts so I'd like to hear are there any straightforward implications which might support or undermine them.

You have a class BPP where problems have a TM with bounded two side error and constant ratio of correct leaves in your computational tree.

You have a class NP, which you can think of there is a TM with computational tree which is correct for no instances , but for yes instance $x$ you can have the correct leaves ration as small as $\frac{1}{2^{p(|x|)}}$.

If you kind of combine this you get for no instances all leaves correct for yes instances only the constant ratio, and this is class RP.

So the conjecture is $RP = NP \cap BPP$. What are the important implications? Is there a 1-line proof?

From me, I can add that the widely believed conjecture $BPP = P$ definitely supports the claim.

Thank you.

**Tags:** complexity-classes
> **Comments:**
> **username_1**: I don't think this conjecture is known. It certainly doesn't have any one line proof.  
> **username_2**: This is not known. However, it is known (and fairly easy) that $\mathrm{NP\subseteq BPP}$ implies $\mathrm{NP=RP}$. I have a déjà-vu feeling that this was already discussed somewhere on this site.  

---

## 0 answers

