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?


1 Answer 1


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 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!

  • $\begingroup$ @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. $\endgroup$ Commented Jan 15, 2020 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.