<p>This isn't my area, so many apologies if I say something incorrect:</p>

<p>1) <strong>"What evidence do we have that <span class="math-container">$\mathsf{BPP}\subseteq \mathsf{REXP}$</span>?"</strong></p>

<p>Isn't this unconditionally true? It should follow from <span class="math-container">$\mathsf{BPP}\subseteq \mathsf{EXP}$</span>, and in fact by Sipser-Gács-Lautemann <span class="math-container">$\mathsf{BPP}\subseteq \Sigma^p_2\cap \Pi_2^p$</span>.</p>

<p>2) <strong>"What consequences does <span class="math-container">$\mathsf{REXP}\subseteq \mathsf{BPP}$</span> give other than what <span class="math-container">$\mathsf{EXP}\subseteq \mathsf{BPP}$</span> gives?"</strong></p>

<p>We always have the following
<span class="math-container">\begin{equation}
\mathsf{P}\subseteq \mathsf{RP}\subseteq \mathsf{NP},\mathsf{BPP}\subseteq \Sigma^p_2\cap \Pi_2^p\subseteq \mathsf{PH}\subseteq \mathsf{EXP}\subseteq \mathsf{REXP}\subseteq \mathsf{NEXP},
\end{equation}</span>
where it is not known how <span class="math-container">$\mathsf{NP}$</span> and <span class="math-container">$\mathsf{BPP}$</span> relate.</p>

<p>Let's assume <span class="math-container">$\mathsf{EXP}\subsetneq \mathsf{REXP}$</span> first. By padding, this should imply (I think) via the contrapositive that <span class="math-container">$\mathsf{P}\subsetneq \mathsf{RP}$</span>. It is also known that <span class="math-container">$\mathsf{NP}\subseteq \mathsf{BPP}$</span> implies <span class="math-container">$\mathsf{NP}=\mathsf{RP}$</span>, which by padding should imply <span class="math-container">$\mathsf{NEXP}=\mathsf{REXP}$</span> (again, I think). So if we only assume <span class="math-container">$\mathsf{EXP}=\mathsf{BPP}$</span> but not <span class="math-container">$\mathsf{REXP}$</span>, the world would have to look like
<span class="math-container">\begin{equation}
\mathsf{P}\subsetneq \mathsf{RP}=\mathsf{NP}\subseteq \mathsf{BPP}=\mathsf{EXP}\subsetneq \mathsf{REXP}=\mathsf{NEXP}.
\end{equation}</span>
I don't see any immediate way to deduce whether the containment <span class="math-container">$\mathsf{NP}\subseteq \mathsf{BPP}$</span> must be proper or not. If it is not, then the polynomial hierarchy (and by extension, <span class="math-container">$\mathsf{EXP}$</span> here) collapses to <span class="math-container">$\mathsf{NP}$</span>, but I suppose it could be the case that the polynomial hierarchy collapses to the second level (via SGL) where this all happens, but not to the first level.</p>

<p>Now, let's suppose that <span class="math-container">$\mathsf{REXP}=\mathsf{BPP}$</span>. Similar reasoning implies the world looks like
<span class="math-container">\begin{equation}
\mathsf{P}\subseteq \mathsf{RP}=\mathsf{NP}\subseteq \mathsf{BPP}=\mathsf{EXP}= \mathsf{REXP}=\mathsf{NEXP}.
\end{equation}</span>
But now the containment <span class="math-container">$\mathsf{NP}\subseteq \mathsf{BPP}$</span> must be proper, as otherwise <span class="math-container">$\mathsf{NP}=\mathsf{NEXP}$</span>, violating the (nondeterministic) Time-Hierarchy Theorem. Similarly, the containment <span class="math-container">$\mathsf{P}\subseteq \mathsf{RP}$</span> must be proper, for otherwise we get <span class="math-container">$\mathsf{P}=\mathsf{NP}$</span>, so the polynomial hierarchy collapses to <span class="math-container">$\mathsf{P}$</span>, and we get here that <span class="math-container">$\mathsf{P}=\mathsf{EXP}$</span>, violating (deterministic) Time-Hierarchy. Therefore, the world would look like</p>

<p><span class="math-container">\begin{equation}
\mathsf{P}\subsetneq \mathsf{RP}=\mathsf{NP}\subsetneq \mathsf{BPP}=\mathsf{EXP}=\mathsf{REXP}=\mathsf{NEXP}
\end{equation}</span>
Apparently there is an oracle relative to which this situation actually happens (see the <a href="https://en.wikipedia.org/wiki/BPP_(complexity)#Relativization" rel="noreferrer">Wikipedia page for BPP</a> and the references there).</p>

<p>So it seems to me that this stronger assumption implies one extra separation that I don't know is implied by the weaker assumption. Hope this helps and is relatively error-free!</p>

CC BY-SA 4.0
2020-01-15T14:37:16.130Z
@VS. I think the answer is no for both. The latter because of the oracle listed in my answer and in the Wikipedia article. The former because there apparently is an oracle $A$ relative to which $\mathsf{P}^A=\mathsf{RP}^A$ but $\mathsf{P}^A\neq \mathsf{BPP}^A$ of Fortnow and Buhrman, see "One-sided Versus Two-sided Error in Probabilistic Computation." Like I said, not even close to an expert, so sadly I don't have a good summary for how this can happen.
Jason Gaitonde
CC BY-SA 4.0
2020-01-11T03:38:33.720Z
2020-01-11T03:38:33.720Z
Jason Gaitonde
<p>From <span class="math-container">$P=RP$</span> extrapolation we might think <span class="math-container">$EXP=REXP$</span>.</p>
<blockquote>
<ol>
<li><p>What evidence do we have <span class="math-container">$BPP\subseteq REXP$</span>?</p>
</li>
<li><p>What consequence <span class="math-container">$REXP\subseteq BPP$</span> gives other than what <span class="math-container">$EXP\subseteq BPP$</span> gives?</p>
</li>
</ol>
</blockquote>

<cc.complexity-theory><randomness><exp-time-algorithms>
Does two-sided error have more capability than one-sided error?
Turbo
# Does two-sided error have more capability than one-sided error?

(Asked by: username_0 on 2020-01-10)

From $P=RP$ extrapolation we might think $EXP=REXP$.

> 1. What evidence do we have $BPP\subseteq REXP$?
> 2. What consequence $REXP\subseteq BPP$ gives other than what $EXP\subseteq BPP$ gives?

**Tags:** cc.complexity-theory, randomness, exp-time-algorithms

---

## 1 answers

### Answer by username_1 on 2020-01-11. Score: 9 | Accepted answer

This isn't my area, so many apologies if I say something incorrect:

1) **"What evidence do we have that $\mathsf{BPP}\subseteq \mathsf{REXP}$?"**

Isn't this unconditionally true? It should follow from $\mathsf{BPP}\subseteq \mathsf{EXP}$, and in fact by Sipser-Gács-Lautemann $\mathsf{BPP}\subseteq \Sigma^p\_2\cap \Pi\_2^p$.

2) **"What consequences does $\mathsf{REXP}\subseteq \mathsf{BPP}$ give other than what $\mathsf{EXP}\subseteq \mathsf{BPP}$ gives?"**

We always have the following
\begin{equation}
\mathsf{P}\subseteq \mathsf{RP}\subseteq \mathsf{NP},\mathsf{BPP}\subseteq \Sigma^p\_2\cap \Pi\_2^p\subseteq \mathsf{PH}\subseteq \mathsf{EXP}\subseteq \mathsf{REXP}\subseteq \mathsf{NEXP},
\end{equation}
where it is not known how $\mathsf{NP}$ and $\mathsf{BPP}$ relate.

Let's assume $\mathsf{EXP}\subsetneq \mathsf{REXP}$ first. By padding, this should imply (I think) via the contrapositive that $\mathsf{P}\subsetneq \mathsf{RP}$. It is also known that $\mathsf{NP}\subseteq \mathsf{BPP}$ implies $\mathsf{NP}=\mathsf{RP}$, which by padding should imply $\mathsf{NEXP}=\mathsf{REXP}$ (again, I think). So if we only assume $\mathsf{EXP}=\mathsf{BPP}$ but not $\mathsf{REXP}$, the world would have to look like
\begin{equation}
\mathsf{P}\subsetneq \mathsf{RP}=\mathsf{NP}\subseteq \mathsf{BPP}=\mathsf{EXP}\subsetneq \mathsf{REXP}=\mathsf{NEXP}.
\end{equation}
I don't see any immediate way to deduce whether the containment $\mathsf{NP}\subseteq \mathsf{BPP}$ must be proper or not. If it is not, then the polynomial hierarchy (and by extension, $\mathsf{EXP}$ here) collapses to $\mathsf{NP}$, but I suppose it could be the case that the polynomial hierarchy collapses to the second level (via SGL) where this all happens, but not to the first level.

Now, let's suppose that $\mathsf{REXP}=\mathsf{BPP}$. Similar reasoning implies the world looks like
\begin{equation}
\mathsf{P}\subseteq \mathsf{RP}=\mathsf{NP}\subseteq \mathsf{BPP}=\mathsf{EXP}= \mathsf{REXP}=\mathsf{NEXP}.
\end{equation}
But now the containment $\mathsf{NP}\subseteq \mathsf{BPP}$ must be proper, as otherwise $\mathsf{NP}=\mathsf{NEXP}$, violating the (nondeterministic) Time-Hierarchy Theorem. Similarly, the containment $\mathsf{P}\subseteq \mathsf{RP}$ must be proper, for otherwise we get $\mathsf{P}=\mathsf{NP}$, so the polynomial hierarchy collapses to $\mathsf{P}$, and we get here that $\mathsf{P}=\mathsf{EXP}$, violating (deterministic) Time-Hierarchy. Therefore, the world would look like

\begin{equation}
\mathsf{P}\subsetneq \mathsf{RP}=\mathsf{NP}\subsetneq \mathsf{BPP}=\mathsf{EXP}=\mathsf{REXP}=\mathsf{NEXP}
\end{equation}
Apparently there is an oracle relative to which this situation actually happens (see the [Wikipedia page for BPP](https://en.wikipedia.org/wiki/BPP_(complexity)#Relativization) and the references there).

So it seems to me that this stronger assumption implies one extra separation that I don't know is implied by the weaker assumption. Hope this helps and is relatively error-free!

> **Comments:**
> **username_1**: @VS. I think the answer is no for both. The latter because of the oracle listed in my answer and in the Wikipedia article. The former because there apparently is an oracle $A$ relative to which $\mathsf{P}^A=\mathsf{RP}^A$ but $\mathsf{P}^A\neq \mathsf{BPP}^A$ of Fortnow and Buhrman, see "One-sided Versus Two-sided Error in Probabilistic Computation." Like I said, not even close to an expert, so sadly I don't have a good summary for how this can happen.  

---

