# Implications of resolving $BPP$ vs $PSPACE$

The relationship between the complexity classes $BPP$, $P$, and $NEXP$ is currently undetermined. We know that $P \neq EXP$ by the time hierarchy theorem, but we don't know if $BPP = P$ (as many believe) or $BPP = EXP$ (considered unlikely) or somewhere in between. But, we do know a few interesting implications that would result from determining this one way or another:

• $P \neq BPP \implies P \neq NP$
• $P = BPP \implies BPP \neq EXP$

and so forth.

What I am wondering is, how does the relationship of $BPP$ to $PSPACE$ affect these relationships?

For instance, we know that $BPP \subset PSPACE$, but it is not known whether $BPP = PSPACE$ (considered unlikely) or $BPP \neq PSPACE$.

If this relationship is finally determined one way or the other, would it have any effect on what we know about the relationship between $BPP$ and $EXP$, on $BPP$ and $P$, on $P$ and $PSPACE$, on $PSPACE$ and $EXP$, or on $P$ and $NP$?

Conversely, would clearing up anything about the undetermined relationships of these other classes imply or lead to a proof that $BPP \neq PSPACE$?

I believe $BPP = PSPACE$ would make $PH$ collapse to at least its second level, which is where $BPP$ is contained; I am not sure if it would collapse entirely.

• 1) There's surely an oracle where BPP=PSPACE=PH, but $P \neq NP$ (and probably even $NP \neq coNP$). 2) If BPP=PSPACE, then NP=RP (since the latter holds whenever NP is in BPP). – Joshua Grochow Jun 2 '18 at 4:17
• @JoshuaGrochow Indeed. There is even an oracle that makes $\mathrm{BPP=EXP^{NP}}$. – Emil Jeřábek 3.0 Jun 2 '18 at 8:57
• @Martin Schwarz: I don't understand the edit here. You changed all references from "NEXP" to "EXP," and say it's because we already know that P != EXP. Why does P != EXP have anything to do with EXP vs NEXP? Furthermore, what do either of these things have to do with BPP? – Mike Battaglia Jun 4 '18 at 15:59
• Ok, I think that makes sense then – Mike Battaglia Jun 4 '18 at 19:12
• If $\mathbf{BPP} \neq \mathbf{PSPACE}$, then $\mathbf{BPP} \neq \mathbf{EXP}$, which implies an average-case subexponential-time derandomization of $\mathbf{BPP}$. – William Hoza Jun 4 '18 at 21:52