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

CC BY-SA 3.0
2012-12-04T16:14:55.450Z
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
CC BY-SA 3.0
2012-12-04T17:07:51.620Z
@TayfunPay: But is $\mathbf{BPP}\subseteq\mathbf{P}$ known to imply $\mathbf{BPP}^{\oplus\mathbf{P}}\subseteq\mathbf{P}^{\oplus\mathbf{P}}$?
Colin McQuillan
CC BY-SA 3.0
2012-12-04T19:45:46.630Z
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
CC BY-SA 3.0
2012-12-04T21:20:13.563Z
@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
CC BY-SA 3.0
2012-12-05T05:00:59.383Z
We know ${\bf P} \subseteq {\bf BPP}$ so if you start talking about  ${\bf BPP}$ contained in ${\bf P}$ then clearly ${\bf BPP}$ cannot be more powerful then ${\bf P}$. It is known than ${\bf PH} \subseteq {\bf BPP^{\oplus P}}$ and that ${\bf \oplus P}$ is not comparable ${\bf PH}$ unless ${\bf PH}$ collapses to a finite level. Assume ${\bf BPP} \subseteq {\bf P}$, then we have ${\bf BPP^{\oplus P}} \subseteq {\bf P^{\oplus P}}$ but we know ${\bf P^{\oplus P}} = {\bf \oplus P}$ thus ${\bf BPP^{\oplus P}} = {\bf \oplus P}$ and ${\bf PH}$ collapses to a finite level.
Tayfun Pay
CC BY-SA 3.0
2012-12-05T10:10:51.343Z
I might be completely wrong, but wouldn't there be a possibility that an oracle O gives more power to a BPP machine than to a $P$ machine? I mean for me is not obvious that $BPP \subseteq P$ implies $BPP^{O}\subseteq P^{O}$, as used in your last argument.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2012-12-05T12:54:26.903Z
@Mateus Does there exists two complexity classes  ${\bf A} \subseteq {\bf P}$ and  ${\bf P} \subseteq {\bf B}$, where ${\bf P^{B} } = {\bf B}$ but it is known that ${\bf A^{B} }$ not necessarily equals $ {\bf B}$?
Tayfun Pay
CC BY-SA 3.0
2012-12-05T17:44:58.960Z
@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
CC BY-SA 3.0
2012-12-05T18:43:23.223Z
@Andras You are right! ${\bf RP}$ is not known to be low for itself or closed under Turing reductions. However, I still think ${\bf BPP} \subseteq {\bf P}$ would mean polynomial hierarchy collapses.. .
Tayfun Pay
CC BY-SA 3.0
2017-10-31T13:18:44.953Z
@TayfunPay If $P=BPP$ is proved, that does *not* imply $P^{\oplus P}=BPP^{\oplus P}$. Some inclusions (such as $P\subseteq NP$) are true relative to all oracles; those inclusions are said to *``relativize''*. (e.g. if $O$ is a (set of) languages, then $P^O\subseteq NP^O$, so $P\subseteq NP$ is a *relativizing* statement) But the interesting containments, like $BPP\subseteq P$, do not relativize. This means that you cannot say that, since $BPP\subseteq P$ under the hypothesis, it follows that $BPP^{\oplus P}\subseteq P^{\oplus P}$.
Lieuwe Vinkhuijzen
CC BY-SA 3.0
2017-10-31T13:26:41.590Z
@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.
Lieuwe Vinkhuijzen
CC BY-SA 3.0
2017-11-03T02:57:58.340Z
@LieuweVinkhuijzen This conversation is 5 years old. Please take date into consideration. Thanks
Tayfun Pay
<complexity-classes><randomized-algorithms><derandomization>
Narrowing the gap between BPP and RP
Andras Farago
# Narrowing the gap between BPP and RP

(Asked by: username_0 on 2012-12-04)

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

**Tags:** complexity-classes, randomized-algorithms, derandomization

> **Comments:**
> **username_1**: 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.  
> **username_2**: @TayfunPay: But is $\mathbf{BPP}\subseteq\mathbf{P}$ known to imply $\mathbf{BPP}^{\oplus\mathbf{P}}\subseteq\mathbf{P}^{\oplus\mathbf{P}}$?  
> **username_1**: 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.  
> **username_3**: @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.  
> **username_1**: We know ${\bf P} \subseteq {\bf BPP}$ so if you start talking about  ${\bf BPP}$ contained in ${\bf P}$ then clearly ${\bf BPP}$ cannot be more powerful then ${\bf P}$. It is known than ${\bf PH} \subseteq {\bf BPP^{\oplus P}}$ and that ${\bf \oplus P}$ is not comparable ${\bf PH}$ unless ${\bf PH}$ collapses to a finite level. Assume ${\bf BPP} \subseteq {\bf P}$, then we have ${\bf BPP^{\oplus P}} \subseteq {\bf P^{\oplus P}}$ but we know ${\bf P^{\oplus P}} = {\bf \oplus P}$ thus ${\bf BPP^{\oplus P}} = {\bf \oplus P}$ and ${\bf PH}$ collapses to a finite level.  
> **username_4**: I might be completely wrong, but wouldn't there be a possibility that an oracle O gives more power to a BPP machine than to a $P$ machine? I mean for me is not obvious that $BPP \subseteq P$ implies $BPP^{O}\subseteq P^{O}$, as used in your last argument.  
> **username_1**: @Mateus Does there exists two complexity classes  ${\bf A} \subseteq {\bf P}$ and  ${\bf P} \subseteq {\bf B}$, where ${\bf P^{B} } = {\bf B}$ but it is known that ${\bf A^{B} }$ not necessarily equals $ {\bf B}$?  
> **username_0**: @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.  
> **username_1**: @Andras You are right! ${\bf RP}$ is not known to be low for itself or closed under Turing reductions. However, I still think ${\bf BPP} \subseteq {\bf P}$ would mean polynomial hierarchy collapses.. .  
> **username_5**: @TayfunPay If $P=BPP$ is proved, that does *not* imply $P^{\oplus P}=BPP^{\oplus P}$. Some inclusions (such as $P\subseteq NP$) are true relative to all oracles; those inclusions are said to *``relativize''*. (e.g. if $O$ is a (set of) languages, then $P^O\subseteq NP^O$, so $P\subseteq NP$ is a *relativizing* statement) But the interesting containments, like $BPP\subseteq P$, do not relativize. This means that you cannot say that, since $BPP\subseteq P$ under the hypothesis, it follows that $BPP^{\oplus P}\subseteq P^{\oplus P}$.  
> **username_5**: @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.  
> **username_1**: @LieuweVinkhuijzen This conversation is 5 years old. Please take date into consideration. Thanks  

---

## 0 answers

