3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Joshua Grochow Jun 2 '18 at 4:17
  • 2
    $\begingroup$ @JoshuaGrochow Indeed. There is even an oracle that makes $\mathrm{BPP=EXP^{NP}}$. $\endgroup$ – Emil Jeřábek Jun 2 '18 at 8:57
  • 1
    $\begingroup$ @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? $\endgroup$ – Mike Battaglia Jun 4 '18 at 15:59
  • 1
    $\begingroup$ Ok, I think that makes sense then $\endgroup$ – Mike Battaglia Jun 4 '18 at 19:12
  • 1
    $\begingroup$ If $\mathbf{BPP} \neq \mathbf{PSPACE}$, then $\mathbf{BPP} \neq \mathbf{EXP}$, which implies an average-case subexponential-time derandomization of $\mathbf{BPP}$. $\endgroup$ – William Hoza Jun 4 '18 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.