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 . (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 in the real world, because Toda’s Theorem implies that , where as Aaronson puts it, “is to as is to .” Since we expect (because of plausible derandomization assumptions) that in real life — and, in general, that randomization does not help much, given these plausible assumptions, then “probably” so by Toda’s Theorem, .

This sounded great to me, but I now realize I have no idea what 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 , that does not mean we can derandomize , 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 does not evaluate to the same truth value under all oracles. So if with respect to some oracle , that “must” mean that the pseudorandom generators do not exist for in , else we could derandomize it. Nisan’s feeling/conjecture is that somewhere in such oracle constructions, there must be an implied upper bound for , keeping it below .

In a nutshell, what is the relationship of derandomization to ?

### Like this:

Like Loading...