Monthly Archives: November 2011

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}?