When does randomization stops helping within PSPACE

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 Jebek 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 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.

Solved by user248 (8,821 )
May 01, 2015 at 05:36