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.