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$?

  • $\begingroup$ 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. $\endgroup$ – Tayfun Pay Dec 4 '12 at 16:14
  • 4
    $\begingroup$ @TayfunPay: But is $\mathbf{BPP}\subseteq\mathbf{P}$ known to imply $\mathbf{BPP}^{\oplus\mathbf{P}}\subseteq\mathbf{P}^{\oplus\mathbf{P}}$? $\endgroup$ – Colin McQuillan Dec 4 '12 at 17:07
  • 1
    $\begingroup$ @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. $\endgroup$ – Kaveh Dec 4 '12 at 21:20
  • 1
    $\begingroup$ @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. $\endgroup$ – Andras Farago Dec 5 '12 at 17:44
  • 1
    $\begingroup$ @TayfunPay In particular, we have discovered a language $A$ such that $P^A\subsetneq BPP^A$. Moreover, under reasonable circuit lower bound conjectures, $P=BPP$ and the polynomial hierarchy is infinite (see Russel-Impagliazzo, 1997). For more on relativization, see either Baker-Gill-Solovay, 1975, or Fortnow 1994 "the role of relativization" or, perhaps the best option, Aaronson-Widgerson 2009 "Algebrization". Hope this helps. $\endgroup$ – Lieuwe Vinkhuijzen Oct 31 '17 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.