Is $PH \subseteq PP$?

Question

We know that the first level of the polynomial hierarchy (i.e. NP and co-NP) is in PP, and that $PP \subseteq PSPACE$. We also know from Toda's Theorem that $PH \subseteq P^{PP}$.

Do we know whether $PH \subseteq PP$? If not, why is it that $P$ with a $PP$ oracle is stronger than $PP$? Is it possible that $PH \nsubseteq PP$ and $PP \nsubseteq PH$?

This question is very simple, but I haven't found any resources addressing it.

I asked this related but much less specific question on math overflow before learning more about the topic.

Here is a somewhat related (but different) question: Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

Update: Take a look at Noam Nisan's question here: More on PH in PP?

Answer 1

Huck, as Lance and Robin pointed out, we do have oracles relative to which PH is not in PP. But that doesn't answer your question, which was what the situation is in the "real" (unrelativized) world!

The short answer is that (as with so much else in complexity theory) we don't know.

But the longer answer is that there are very good reasons to conjecture that indeed PH ⊆ PP.

First, Toda's Theorem implies PH ⊆ BP.PP, where BP.PP is the complexity class that "is to PP as BPP is to P" (in other words, PP where you can use a randomization to decide which MAJORITY computation you want to perform). Second, under plausible derandomization hypotheses (similar to the ones that are known to imply P=BPP, by Nisan-Wigderson, Impagliazzo-Wigderson, etc.), we would have PP = BP.PP.

Addendum, to address your other questions:

(1) I'd say that we don't have a compelling intuition either way on the question of whether PP = P^PP. We know, from the results of Beigel-Reingold-Spielman and Fortnow-Reingold, that PP is closed under nonadaptive (truth-table) reductions. In other words, a P machine that can make parallel queries to a PP oracle is no more powerful than PP itself. But the fact that these results completely break down for adaptive (non-parallel) queries to the PP oracle suggests that maybe the latter are really more powerful.

(2) Likewise, NP^PP and coNP^PP might be still more powerful than P^PP. And PP^PP might be more powerful still, and so on. The sequence P, PP, P^PP, PP^PP, P^{PP^PP}, etc. is called the counting hierarchy, and just as people conjecture that PH is infinite, so too one can conjecture (though maybe with less confidence!) that CH is infinite. This is closely related to the belief that, in constant-depth threshold circuits (i.e., neural networks), adding more layers of threshold gates gives you more computational power.

Answer 2

Richard Beigel has an oracle relative to which $P^{NP}$ is not contained in PP.

Answer 3

Vereshchagin [Ver] showed that there is an oracle relative to which AM is not contained in PP. (This result seems incomparable with the $P^{NP}$ vs PP result.)

[Ver] N. K. Vereshchagin. On the power of PP, Proceedings of IEEE Complexity'92, pp. 138-143, 1992.

Answer 4

Something that has not been mentioned so far (as far as I can see) and that holds in the unrelativized world is the following:

$$PH \subseteq PP \quad\mbox{ if }\quad QMA = PP.$$

This was observed by Vyalyi in this paper and comes from the strengthening of two theorems:

1. Toda's theorem - Vyalyi shows that one query to a $\sharp P$ oracle is enough for a "$P$ machine" to simulate $PH$.
2. The inclusion $QMA \subseteq PP$ proved by Kitaev and Watrous. Vyalyi proves that $QMA$ is also in $A_0PP$, a class that is contained in $PP$.