37
$\begingroup$

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?

$\endgroup$
37
$\begingroup$

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 = PPP. 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, NPPP and coNPPP might be still more powerful than PPP. And PPPP might be more powerful still, and so on. The sequence P, PP, PPP, PPPP, PPP^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.

$\endgroup$
  • 7
    $\begingroup$ Scott, I'm a bit confused by the statement that "plausibly" PP will contain PH. The first separation of PH from PP via oracles has at its combinatorial core the original Minski&Papert separation that an AND-of-ORs can not be simulated by a polylog-degree threshold gate. I think that the non-uniform version of Toda is simulating AC0 by a probability distribution over polylog-degree threshold gates which gets the correct answer whp. Thus at the non-uniform level the "BP"-gate adds significant power, unlike for non-uniform P vs BPP or NP vs AM. So for example is PH in PP with a random oracle? $\endgroup$ – Noam Nov 24 '10 at 19:27
  • $\begingroup$ Noam, doesn't PP with a random oracle contain BP.PP? (I don't see why it shouldn't.) If so, then sure PH is in PP with random oracle. But let me ask another question: is there any complexity class C for which we have good reasons to believe that C doesn't equal BP.C? $\endgroup$ – Scott Aaronson Nov 24 '10 at 21:39
  • $\begingroup$ You would need amplification to show that PP=BP.PP with a random oracle -- I don't see how to do that. Even non-uniformly, I can't see that PH is in PP/poly. Wouldn't the AND-of-ORs not in polylog-degree-threshold seem to suggest that even non-uniformly PH is not in PP? $\endgroup$ – Noam Nov 25 '10 at 4:56
  • $\begingroup$ Here's a paper that shows BP.PP=PP under a plausible hypothesis: www.cs.uwyo.edu/~jhitchco/papers/hhdcc.ps $\endgroup$ – Scott Aaronson Nov 25 '10 at 17:46
  • 8
    $\begingroup$ What I missing was that Fortnow and Reingold showed that PP is closed under truthtable reductions, a closure which is needed for derandomization using a PRG (or non-uniformly or with a random oracle). However I am still puzzled here, and formulated a question about it: cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp $\endgroup$ – Noam Nov 26 '10 at 9:23
23
$\begingroup$

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

$\endgroup$
20
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.