Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 6 down vote favorite

We do not know yet whether the 2-sided error of $BPP$ allows more computing power than the one sided error of $RP$. In view of derandomization results, the conjectured answer is no, since both classes are conjectured to collapse into $P$. However, not having a proof of that yet, I wonder if there are any results that at least bring $BPP$ closer to $RP$. For example, is there any condition that is known to imply $BPP=RP\cup co-RP$, or $BPP=P^{RP}$, or something similar, but is not known to imply $BPP=RP$?

share|improve this question
Toda showed that ${\bf PH} \subseteq {\bf BPP^{\oplus P}}$. So if ${\bf BPP} \subseteq {\bf P}$ Then we have ${\bf PH} \subseteq {\bf P^{\bf \oplus P}}$. However, ${\bf \oplus P}$ is low for itself so then we will have ${\bf PH} \subseteq {\bf \oplus P}$. But Toda also showed that ${\bf PH}$ is comparable to ${\bf \oplus P}$ if and only if ${\bf PH}$ collapses to a finite level. As far as I understand ${\bf BPP} \subseteq {\bf P}$ implies that ${\bf PH }$ collapses to a finite level. – Tayfun Pay Dec 4 '12 at 16:14
3  
@TayfunPay: But is $\mathbf{BPP}\subseteq\mathbf{P}$ known to imply $\mathbf{BPP}^{\oplus\mathbf{P}}\subseteq\mathbf{P}^{\oplus\mathbf{P}}$? – Colin McQuillan Dec 4 '12 at 17:07
It is known that ${\bf {\oplus P}^{\oplus P}} = {\bf \oplus P} $ and ${\bf {P}^{\oplus P}} = {\bf \oplus P} $. It is further known that ${\bf {BPP}^{BPP}} = {\bf BPP} $ and ${\bf {P}^{BPP}} = {\bf BPP} $. So I believe it holds. – Tayfun Pay Dec 4 '12 at 19:45
1  
@Tayfun, $\mathsf{BPP}$ with an oracle is a delicate class. Take for example the interactive proof version of it: $\mathsf{IP}$. Although $\mathsf{PSpace} \subseteq \mathsf{IP}$, almost surely $\mathsf{PSpace}^O \not \subseteq \mathsf{IP}^O$. It seems that the relativized version of bounded error classes become weaker, so I guess that is true, but I think a similar issue might be at play in relativizing the non-interactive case as well. Would be interested if you have a reference for the implication. – Kaveh♦ Dec 4 '12 at 21:20
1  
@TayfunPay, I do not see why $P^{RP}=RP$ should hold, since $co-RP\subseteq P^{RP}$, so the $P^{RP}=RP$ equality would collapse $RP$ into $ZPP$. That collapse is currently not known, and proving it would be a breakthrough. – Andras Farago Dec 5 '12 at 17:44
show 4 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.