<p>Richard Beigel has an <a href="http://knight.cis.temple.edu/~beigel/papers/delta2p-cc.html">oracle</a> relative to which $P^{NP}$ is not contained in PP.</p>

CC BY-SA 2.5
2010-11-23T12:05:53.790Z
2010-11-23T12:05:53.790Z
Lance Fortnow
<p>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.)</p>

<p>[Ver] N. K. Vereshchagin. <a href="http://lpcs.math.msu.su/~ver/papers/am-pp.ps" rel="nofollow">On the power of PP</a>, Proceedings of IEEE Complexity'92, pp. 138-143, 1992. </p>

CC BY-SA 3.0
2010-11-23T21:38:00.250Z
2013-03-19T17:56:47.710Z
2013-03-19T17:56:47.710Z
Robin Kothari
<p>Something that has not been mentioned so far (as far as I can see) and that holds in the unrelativized world is the following:</p>

<p>$$PH \subseteq PP \quad\mbox{ if }\quad QMA = PP.$$</p>

<p>This was observed by Vyalyi in <a href="http://eccc.hpi-web.de/report/2003/021">this paper</a> and comes from the strengthening of two theorems:</p>

<ol>
<li>Toda's theorem - Vyalyi shows that <em>one query</em> to a $\sharp P$ oracle is enough for a "$P$ machine" to simulate $PH$.</li>
<li>The inclusion $QMA \subseteq PP$ proved by Kitaev and Watrous. Vyalyi proves that $QMA$ is also in <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aA#a0pp">$A_0PP$</a>, a class that is contained in $PP$.</li>
</ol>

CC BY-SA 3.0
2013-01-21T22:53:05.860Z
2013-01-21T23:17:36.800Z
2013-01-21T23:17:36.800Z
Alessandro Cosentino
<p>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!</p>

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

<p>But the longer answer is that there are very good reasons to conjecture that indeed PH &sube; PP.</p>

<p>First, Toda's Theorem implies PH &sube; 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.</p>

<p><b>Addendum,</b> to address your other questions:</p>

<p>(1) I'd say that we don't have a compelling intuition either way on the question of whether PP = P<sup>PP</sup>.  We know, from the results of Beigel-Reingold-Spielman and Fortnow-Reingold, that PP is closed under <i>nonadaptive</i> (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 <i>adaptive</i> (non-parallel) queries to the PP oracle suggests that maybe the latter are really more powerful.</p>

<p>(2) Likewise, NP<sup>PP</sup> and coNP<sup>PP</sup> might be still more powerful than P<sup>PP</sup>.  And PP<sup>PP</sup> might be more powerful still, and so on.  The sequence P, PP, P<sup>PP</sup>, PP<sup>PP</sup>, P<sup>PP^PP</sup>, etc. is called the <i>counting hierarchy</i>, 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.</p>

CC BY-SA 2.5
2010-11-24T19:27:03.163Z
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?
Noam
CC BY-SA 2.5
2010-11-24T21:39:16.733Z
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?
Scott Aaronson
CC BY-SA 2.5
2010-11-25T04:56:34.513Z
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?
Noam
CC BY-SA 2.5
2010-11-25T17:46:59.683Z
Here's a paper that shows BP.PP=PP under a plausible hypothesis: www.cs.uwyo.edu/~jhitchco/papers/hhdcc.ps
Scott Aaronson
CC BY-SA 2.5
2010-11-25T19:01:47.310Z
I'm not totally sure that this paper addresses the issue at hand: as far as I can tell, the PP result is peripheral in the paper and the heart of proof of the derandomization of PP in the paper is "use a PRG just as in [5]" which does not seem to address the issue of amplification.  Most of the effort in the paper is to get a suitable PRG from their assumptions but I don't see how to do the derandomization even given a perfect PRG (which you get for free in a non-uniform model).
Noam
CC BY-SA 2.5
2010-11-25T21:15:24.307Z
OK, then here's another paper claiming to show that PH is contained in PP (and even the subclass SPP) under a plausible derandomization assumption: www.cs.uwyo.edu/~jhitchco/papers/sspp.ps .  See if you like this one better! :)  Look, I mostly just knew these papers existed -- if you're claiming that there's an error in them having to do with amplification, I'll have to think about that more carefully (emailing the authors wouldn't hurt either...).
Scott Aaronson
CC BY-SA 2.5
2010-11-26T09:23:21.553Z
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: http://cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp
Noam
CC BY-SA 3.0
2010-11-24T11:35:55.490Z
2013-03-23T15:38:35.713Z
2013-03-23T15:38:35.713Z
Scott Aaronson
<p>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 <a href="http://en.wikipedia.org/wiki/Toda%27s_theorem" rel="noreferrer">Toda's Theorem</a> that $PH \subseteq P^{PP}$.</p>

<p>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$?</p>

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

<p>I asked <a href="https://mathoverflow.net/questions/39690/how-is-p-related-to-other-complexity-classes">this</a> related but much less specific question on math overflow before learning more about the topic.</p>

<p>Here is a somewhat related (but different) question: <a href="https://cstheory.stackexchange.com/questions/2559/is-conp-pnp-pp-p">Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?</a></p>

<p><strong>Update:</strong> Take a look at Noam Nisan's question here: <a href="https://cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp">More on PH in PP?</a></p>

<cc.complexity-theory><counting-complexity><polynomial-hierarchy>
Is $PH \subseteq PP$?
Huck Bennett
# Is $PH \subseteq PP$?

(Asked by: username_0 on 2010-11-23)

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](http://en.wikipedia.org/wiki/Toda%27s_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](https://mathoverflow.net/questions/39690/how-is-p-related-to-other-complexity-classes) 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}$?](https://cstheory.stackexchange.com/questions/2559/is-conp-pnp-pp-p)

**Update:** Take a look at Noam Nisan's question here: [More on PH in PP?](https://cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp)

**Tags:** cc.complexity-theory, counting-complexity, polynomial-hierarchy

---

## 4 answers

### Answer by username_4 on 2010-11-24. Score: 40 | Accepted answer

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.

> **Comments:**
> **username_5**: 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?  
> **username_4**: 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?  
> **username_5**: 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?  
> **username_4**: Here's a paper that shows BP.PP=PP under a plausible hypothesis: www.cs.uwyo.edu/~jhitchco/papers/hhdcc.ps  
> **username_5**: I'm not totally sure that this paper addresses the issue at hand: as far as I can tell, the PP result is peripheral in the paper and the heart of proof of the derandomization of PP in the paper is "use a PRG just as in [5]" which does not seem to address the issue of amplification.  Most of the effort in the paper is to get a suitable PRG from their assumptions but I don't see how to do the derandomization even given a perfect PRG (which you get for free in a non-uniform model).  
> **username_4**: OK, then here's another paper claiming to show that PH is contained in PP (and even the subclass SPP) under a plausible derandomization assumption: www.cs.uwyo.edu/~jhitchco/papers/sspp.ps .  See if you like this one better! :)  Look, I mostly just knew these papers existed -- if you're claiming that there's an error in them having to do with amplification, I'll have to think about that more carefully (emailing the authors wouldn't hurt either...).  
> **username_5**: 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: http://cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp  

---

### Answer by username_1 on 2010-11-23. Score: 23

Richard Beigel has an [oracle](http://knight.cis.temple.edu/~beigel/papers/delta2p-cc.html) relative to which $P^{NP}$ is not contained in PP.


---

### Answer by username_2 on 2010-11-23. Score: 20

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](http://lpcs.math.msu.su/~ver/papers/am-pp.ps), Proceedings of IEEE Complexity'92, pp. 138-143, 1992.


---

### Answer by username_3 on 2013-01-21. Score: 14

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](http://eccc.hpi-web.de/report/2003/021) 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$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aA#a0pp), a class that is contained in $PP$.


---

