# Can we derandomize BP.PP?

Two days ago, I added a “bounty” to a year-old unanswered question that Noam Nisan asked on CSTheory about the relationship between the Polynomial Hierarchy and the complexity class PP (probabilistic polynomial time).  I remember thinking when the question was first asked, “Wow, there is something important going on here,” but no one has posted an answer, even though the question has received a thousand views.  I hope this blog entry can drive a bit more traffic that direction, because I bet someone, somewhere does know the answer — and I am quite confident that person isn’t me!

The issue, as I understand it, is whether the polynomial hierarchy (PH) is contained within PP in “the real world.”  There exist oracles (possible worlds) in which $\textsf{PH} \subsetneq \textsf{PP}$.  (See the answers to this question of Huck Bennett for references and explanation.)  On the other hand, Scott Aaronson in this answer makes the case for $\textsf{PH} \subseteq \textsf{PP}$ in the real world, because Toda’s Theorem implies that $\textsf{PH} \subseteq \textsf{BP.PP}$, where $\textsf{BP.PP}$ as Aaronson puts it, “is to $\textsf{PP}$ as $\textsf{BPP}$ is to $\textsf{P}$.”  Since we expect (because of plausible derandomization assumptions) that $\textsf{BPP}=\textsf{P}$ in real life — and, in general, that randomization does not help much, given these plausible assumptions, then “probably” $\textsf{BP.PP}=\textsf{PP}$ so by Toda’s Theorem, $\textsf{PH} \subseteq \textsf{PP}$.

This sounded great to me, but I now realize I have no idea what $\textsf{BP.PP}$ is, not really.  Fortunately for my ego, this seems to be the crux of Nisan’s question.  His point, as I understand it, is that just because we expect to be able to derandomize $\textsf{BPP}$, that does not mean we can derandomize $\textsf{BP.PP}$, precisely because the oracles I mentioned at the beginning exist.  Known derandomization techniques seem to relativize (that is, they give the same results with respect to all oracles), and Aaronson’s claim implies that $\textsf{PH} \subseteq \textsf{PP}$ does not evaluate to the same truth value under all oracles.  So if $\textsf{PH} \subsetneq \textsf{PP}$ with respect to some oracle $A$, that “must” mean that the pseudorandom generators do not exist for $\textsf{BP.PP}$ in $A$, else we could derandomize it.  Nisan’s feeling/conjecture is that somewhere in such oracle constructions, there must be an implied upper bound for $\textsf{PP}$, keeping it below $\textsf{PH}$.

In a nutshell, what is the relationship of derandomization to $\textsf{BP.PP}$?