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

<ul>
<li>$P \neq BPP \implies P \neq NP$</li>
<li>$P = BPP \implies BPP \neq EXP$</li>
</ul>

<p>and so forth.</p>

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

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

<p>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$?</p>

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

<p>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.</p>

CC BY-SA 4.0
2018-06-02T04:17:10.637Z
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
CC BY-SA 4.0
2018-06-02T08:57:27.340Z
@JoshuaGrochow Indeed. There is even an oracle that makes $\mathrm{BPP=EXP^{NP}}$.
Emil Jeřábek
CC BY-SA 4.0
2018-06-04T15:59:38.820Z
@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
CC BY-SA 4.0
2018-06-04T18:51:08.077Z
@MikeBattaglia: I think part of the point is that basically everything you said about NEXP applies to EXP just as well. By making the question about EXP instead, it separates out the question you were asking about BPP vs PSPACE from the (seemingly independent) EXP vs NEXP question.
Joshua Grochow
CC BY-SA 4.0
2018-06-04T19:12:02.570Z
Ok, I think that makes sense then
Mike Battaglia
CC BY-SA 4.0
2018-06-04T21:52:49.393Z
If $\mathbf{BPP} \neq \mathbf{PSPACE}$, then $\mathbf{BPP} \neq \mathbf{EXP}$, which [implies](https://www.sciencedirect.com/science/article/pii/S0022000001917805) an average-case subexponential-time derandomization of $\mathbf{BPP}$.
William Hoza
CC BY-SA 4.0
2018-06-08T02:12:57.507Z
$P=BPP$ also means $BPP=BQP$, meaning quantum computers would have the same amount of power as their classical counterparts.
Mike Battaglia
<cc.complexity-theory><complexity><pspace>
Implications of resolving $BPP$ vs $PSPACE$
Mike Battaglia
# Implications of resolving $BPP$ vs $PSPACE$

(Asked by: username_0 on 2018-06-01)

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.

**Tags:** cc.complexity-theory, complexity, pspace
> **Comments:**
> **username_1**: 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).  
> **username_2**: @JoshuaGrochow Indeed. There is even an oracle that makes $\mathrm{BPP=EXP^{NP}}$.  
> **username_0**: @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?  
> **username_1**: @MikeBattaglia: I think part of the point is that basically everything you said about NEXP applies to EXP just as well. By making the question about EXP instead, it separates out the question you were asking about BPP vs PSPACE from the (seemingly independent) EXP vs NEXP question.  
> **username_0**: Ok, I think that makes sense then  
> **username_3**: If $\mathbf{BPP} \neq \mathbf{PSPACE}$, then $\mathbf{BPP} \neq \mathbf{EXP}$, which [implies](https://www.sciencedirect.com/science/article/pii/S0022000001917805) an average-case subexponential-time derandomization of $\mathbf{BPP}$.  
> **username_0**: $P=BPP$ also means $BPP=BQP$, meaning quantum computers would have the same amount of power as their classical counterparts.  

---

## 0 answers

