<p>There is a difficulty with the premise of your question &mdash; "when does randomization stops helping within $\mathrm{PSPACE}$ &mdash; because it suggests that the computational classes $\mathrm{X}$ such that $\mathrm{P \subseteq X \subseteq PSPACE}$ form some sort of linear hierarchy when this is not evident.</p>

<p>We can illustrate this by comparisons between the polynomial hierarchy and counting classes. As Emil Jeřábek indicates in the comments,
   $$\begin{align*} \mathrm{BP\cdot \Sigma_i^p \subseteq \Pi_{i+1}^p} &amp;&amp;\text{and}&amp;&amp;  \mathrm{BP\cdot \Pi_i^p \subseteq \Sigma_{i+1}^p} \end{align*}$$ 
 by relativisation of $\mathrm{AM \subseteq \Pi_2^p}\,$; and therefore $\mathrm{BP \cdot PH = PH}$. On the other hand, <a href="http://en.wikipedia.org/wiki/Toda%27s_theorem#Proof">Toda's Theorem</a> shows that
$$\mathrm{PH \subseteq BP\cdot\oplus P}.$$
If you suppose that "randomization has stopped adding power by the time you ascend to $\mathrm{PH}$", then you will be tempted to suspect that because $\mathrm{PH \subseteq BP \cdot \oplus P}$, perhaps in fact $\mathrm{BP \cdot \oplus P = \oplus P}$. But I don't know that anyone conjectures this, or even that $\mathrm{PH \subseteq \oplus P}$ (which would be a necessary consequence); I think that any result of this sort would be considered a major breakthrough.</p>

<p>Of course, if you only care about the polynomial hierarchy, and more generally (to scale up to $\mathrm{PSPACE}$) quantified boolean formulas, then you can extract some sort of linear answer to your question &mdash; in which case Emil's comments are about as complete an answer as you are likely to get.</p>

CC BY-SA 3.0
2015-05-01T05:40:45.457Z
Thanks! I was indeed thinking more of the polynomial hierarchy than other classes. In fact, this question stems from studying restrictions of temporal logics, so there is some sort of hierarchy among them, and counting classes are less relevant.
Shaull
CC BY-SA 3.0
2015-05-01T06:18:11.293Z
You may want to find a more pointed version of your question then, and try again. :-)
Niel de Beaudrap
CC BY-SA 3.0
2015-05-01T10:47:04.890Z
Concerning the "randomization has stopped adding power" point: we also have $\mathrm{BP\cdot BPP=BPP}$, but this doesn't imply $\mathrm{BP}\cdot\mathcal C=\mathcal C$ for all classes $\mathcal C\supseteq\mathrm{BPP}$.
Emil Jeřábek
CC BY-SA 3.0
2015-05-02T04:38:55.230Z
@Emil: sure enough, though a fair complaint may be that there's already randomness there. This raises the question of whether (for any class, however specified) one can tell whether it already 'contains randomness', but that's a much more complicated kettle of fish.
Niel de Beaudrap
CC BY-SA 3.0
2015-05-01T05:36:04.613Z
2015-05-01T06:27:31.900Z
2015-05-01T06:27:31.900Z
Niel de Beaudrap
<p>It is known that adding bounded-error randomization to PSPACE doesn't add power. That is, BPPSAPCE=PSPACE.</p>

<p>It is famously unknown whether P=BPP, but it is known that $BPP\subseteq \Sigma_2\cap \Pi_2$.</p>

<p>Thus, it is possible (while conjectured to be false) that adding probability to P adds expressive power.</p>

<p>My question is whether we know (or have evidence of) the border between P and PSPACE where adding randomization no longer adds power.</p>

<p>Specifically, </p>

<blockquote>
  <p>Are there any problems that are known to be in $BP\Sigma_i$ (resp. $BP\Pi_i$) that are not known to be in $\Sigma_i$ (resp. $\Pi_i$)? And similarly for $BPPH$ v.s. $PH$?</p>
</blockquote>

CC BY-SA 3.0
2015-04-30T10:49:41.710Z
BPPH=PH. xxxxxxxxxxxxx
Emil Jeřábek
CC BY-SA 3.0
2015-04-30T11:28:20.740Z
@EmilJeřábek - thanks, do you have a reference for this result?
Shaull
CC BY-SA 3.0
2015-04-30T14:11:38.020Z
This is just a relativization of the Gács–Sipser–Lautemann theorem.
Emil Jeřábek
CC BY-SA 3.0
2015-04-30T15:06:34.813Z
Though for a tighter bound, it’s better to relativize the inclusion $\mathrm{AM}\subseteq\Pi^P_2$, which gives $\mathrm{BP}\Sigma^P_i\subseteq\Pi^P_{i+1}$ (for $i\ge1$), and dually $\mathrm{BP}\Pi^P_i\subseteq\Sigma^P_{i+1}$.
Emil Jeřábek
<randomness><derandomization><polynomial-hierarchy>
When does randomization stops helping within PSPACE
Shaull
# When does randomization stops helping within PSPACE

(Asked by: username_0 on 2015-04-30)

It is known that adding bounded-error randomization to PSPACE doesn't add power. That is, BPPSAPCE=PSPACE.

It is famously unknown whether P=BPP, but it is known that $BPP\subseteq \Sigma\_2\cap \Pi\_2$.

Thus, it is possible (while conjectured to be false) that adding probability to P adds expressive power.

My question is whether we know (or have evidence of) the border between P and PSPACE where adding randomization no longer adds power.

Specifically,

> Are there any problems that are known to be in $BP\Sigma\_i$ (resp. $BP\Pi\_i$) that are not known to be in $\Sigma\_i$ (resp. $\Pi\_i$)? And similarly for $BPPH$ v.s. $PH$?

**Tags:** randomness, derandomization, polynomial-hierarchy
> **Comments:**
> **username_1**: BPPH=PH. xxxxxxxxxxxxx  
> **username_0**: @EmilJeřábek - thanks, do you have a reference for this result?  
> **username_1**: This is just a relativization of the Gács–Sipser–Lautemann theorem.  
> **username_1**: Though for a tighter bound, it’s better to relativize the inclusion $\mathrm{AM}\subseteq\Pi^P_2$, which gives $\mathrm{BP}\Sigma^P_i\subseteq\Pi^P_{i+1}$ (for $i\ge1$), and dually $\mathrm{BP}\Pi^P_i\subseteq\Sigma^P_{i+1}$.  

---

## 1 answers

### Answer by username_2 on 2015-05-01. Score: 9 | Accepted answer

There is a difficulty with the premise of your question — "when does randomization stops helping within $\mathrm{PSPACE}$ — because it suggests that the computational classes $\mathrm{X}$ such that $\mathrm{P \subseteq X \subseteq PSPACE}$ form some sort of linear hierarchy when this is not evident.

We can illustrate this by comparisons between the polynomial hierarchy and counting classes. As Emil Jeřábek indicates in the comments,
$$\begin{align\*} \mathrm{BP\cdot \Sigma\_i^p \subseteq \Pi\_{i+1}^p} &&\text{and}&& \mathrm{BP\cdot \Pi\_i^p \subseteq \Sigma\_{i+1}^p} \end{align\*}$$
by relativisation of $\mathrm{AM \subseteq \Pi\_2^p}\,$; and therefore $\mathrm{BP \cdot PH = PH}$. On the other hand, [Toda's Theorem](http://en.wikipedia.org/wiki/Toda%27s_theorem#Proof) shows that
$$\mathrm{PH \subseteq BP\cdot\oplus P}.$$
If you suppose that "randomization has stopped adding power by the time you ascend to $\mathrm{PH}$", then you will be tempted to suspect that because $\mathrm{PH \subseteq BP \cdot \oplus P}$, perhaps in fact $\mathrm{BP \cdot \oplus P = \oplus P}$. But I don't know that anyone conjectures this, or even that $\mathrm{PH \subseteq \oplus P}$ (which would be a necessary consequence); I think that any result of this sort would be considered a major breakthrough.

Of course, if you only care about the polynomial hierarchy, and more generally (to scale up to $\mathrm{PSPACE}$) quantified boolean formulas, then you can extract some sort of linear answer to your question — in which case Emil's comments are about as complete an answer as you are likely to get.

> **Comments:**
> **username_0**: Thanks! I was indeed thinking more of the polynomial hierarchy than other classes. In fact, this question stems from studying restrictions of temporal logics, so there is some sort of hierarchy among them, and counting classes are less relevant.  
> **username_2**: You may want to find a more pointed version of your question then, and try again. :-)  
> **username_1**: Concerning the "randomization has stopped adding power" point: we also have $\mathrm{BP\cdot BPP=BPP}$, but this doesn't imply $\mathrm{BP}\cdot\mathcal C=\mathcal C$ for all classes $\mathcal C\supseteq\mathrm{BPP}$.  
> **username_2**: @Emil: sure enough, though a fair complaint may be that there's already randomness there. This raises the question of whether (for any class, however specified) one can tell whether it already 'contains randomness', but that's a much more complicated kettle of fish.  

---

