<p>Scott Aaronson gives an oracle where $\oplus$P = PEXP which implies the oracle you want. <a href="http://eccc.hpi-web.de/report/2005/040/download/">http://eccc.hpi-web.de/report/2005/040/download/</a> (Theorem 12 in the appendix)</p>

CC BY-SA 3.0
2013-03-24T22:21:34.370Z
Thanks.  I have to choose just one answer to accept so I'm choosing Robin Kothari's answer because it's an earlier reference.
Timothy Chow
CC BY-SA 3.0
2013-03-24T03:27:33.720Z
2013-03-24T03:27:33.720Z
Lance Fortnow
<p>It says that <span class="math-container">$\oplus P \subseteq PP$</span> on page 293 in chapter &quot;A Rogues' Gallery of Complexity Classes&quot; of &quot;The Complexity Theory Companion&quot;. However, they do not provide a reference to it. You can see the snapshot of the said page below.</p>
<p><a href="https://i.sstatic.net/50cEOVHO.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/50cEOVHO.png" alt="enter image description here" /></a></p>
<p>However, it also says that there are oracles relative to which <span class="math-container">$\oplus P \not\subseteq PP$</span> on page 259 in chapter &quot;Polynomial Techniques&quot; in section &quot;9.4 OPEN ISSUE: Is PP Closed Under
Polynomial-Time Turing Reductions? &quot; of the same book. Once again, without any reference. You can see the snap shot below.
<a href="https://i.sstatic.net/WxXG5ifw.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/WxXG5ifw.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2024-05-30T16:13:36.990Z
Thanks for this information! But I'm not sure I believe the assertion here that $\oplus P \subseteq PP$. If it's really a theorem then I would expect it to be a significant result with a citable reference.
Timothy Chow
CC BY-SA 4.0
2024-05-30T17:08:16.843Z
@TimothyChow I did check the errata of it, which can be found here https://www.cs.rochester.edu/u/lane/=companion/ and did not see it being mentioned over there. So I am not quite sure either. Ok
Tayfun Pay
CC BY-SA 4.0
2024-05-31T08:54:22.457Z
This is most certainly a typo. Besides the lack of references, they surely would not write “$\oplus\mathrm P$ is included in $\mathrm{P^{PP}}$” and mention it as somehow relevant to the PP vs. $\mathrm{P^{PP}}$ problem if they actually thought that $\oplus\mathrm{P\subseteq PP}$ has been proven. You should email them so that they can include it in the errata.
Emil Jeřábek
CC BY-SA 4.0
2024-12-04T10:11:30.873Z
I also have serious doubts about “Fact 7”. Neither inclusion seems to follow from anything I saw in Chapter 4, including the notes at the end, and taken together (using also that relativized BPP is low for itself) they would imply $\mathrm{BPP^{PP}=P^{PP}}$, which I strongly suspect to be an open problem.
Emil Jeřábek
CC BY-SA 4.0
2024-05-30T14:27:30.850Z
2024-05-30T14:27:30.850Z
Tayfun Pay
<p>Yes, there is an oracle $A$ such that $\oplus P^A \not\subseteq PP^A$. In fact, there is an oracle $A$ such that $\oplus P^A \not\subseteq PP^{PH^A}$. You can find the result in the following paper.</p>

<blockquote>
  <p>Frederic Green, An oracle separating $\oplus P$ from $PP^{PH}$, Information Processing Letters, Volume 37, Issue 3, 18 February 1991, Pages 149-153</p>
</blockquote>

CC BY-SA 3.0
2013-03-24T22:20:13.380Z
Thanks...this is exactly what I was looking for!  In the opening comments to his paper, Green credits Jacobo Torán's Ph.D. thesis with the first oracle $A$ such that $\oplus P^A \not\subseteq PP^A$. This result was subsequently published as Theorem 5.13 in Torán's paper "Complexity classes defined by counting quantifiers," JACM 38 (1991), 752–773.
Timothy Chow
CC BY-SA 3.0
2013-03-24T03:29:05.207Z
2013-03-24T03:29:05.207Z
Robin Kothari
<p>This question was asked by Jan Pax on the <a href="http://www.cs.nyu.edu/pipermail/fom/2013-March/017135.html" rel="nofollow noreferrer">Foundations of Mathematics mailing list</a>.
Certainly $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$
but I suspect from the answers to <a href="https://cstheory.stackexchange.com/questions/209/best-known-joint-containments-for-by-np-and-parity-p">this question</a> that it's not known whether $\oplus P \subseteq PP$ (otherwise, $PP$ would be one possible answer to that question).  If it's not known, is there an oracle separation?</p>

CC BY-SA 3.0
2013-03-24T01:05:41.600Z
Wikipedia says that there is an oracle for which $P^A = \oplus P^A  \neq NP^A ( = PP^A) = EXP^A$ ( [R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions](http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf) )
Marzio De Biasi
CC BY-SA 3.0
2013-03-24T02:09:43.797Z
Thanks, Marzio.  I guess I should have been more specific: Is there an oracle $A$ such that $\oplus P^A \not\subseteq PP^A$?
Timothy Chow
CC BY-SA 3.0
2013-03-24T14:24:05.860Z
What I am going to say is subsumed by the other answers, but may be useful if you want to keep things simple. The oracle you are looking for is just an application of the old-known fact that a perceptron can not compute PARITY (Minsky & Papert).
Alessandro Cosentino
<cc.complexity-theory><complexity-classes>
Is Parity-P contained in PP?
Timothy Chow
# Is Parity-P contained in PP?

(Asked by: username_0 on 2013-03-23)

This question was asked by Jan Pax on the [Foundations of Mathematics mailing list](http://www.cs.nyu.edu/pipermail/fom/2013-March/017135.html).
Certainly $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$
but I suspect from the answers to [this question](https://cstheory.stackexchange.com/questions/209/best-known-joint-containments-for-by-np-and-parity-p) that it's not known whether $\oplus P \subseteq PP$ (otherwise, $PP$ would be one possible answer to that question). If it's not known, is there an oracle separation?

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: Wikipedia says that there is an oracle for which $P^A = \oplus P^A  \neq NP^A ( = PP^A) = EXP^A$ ( [R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions](http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf) )  
> **username_0**: Thanks, Marzio.  I guess I should have been more specific: Is there an oracle $A$ such that $\oplus P^A \not\subseteq PP^A$?  
> **username_2**: What I am going to say is subsumed by the other answers, but may be useful if you want to keep things simple. The oracle you are looking for is just an application of the old-known fact that a perceptron can not compute PARITY (Minsky & Papert).  

---

## 3 answers

### Answer by username_6 on 2013-03-24. Score: 15 | Accepted answer

Yes, there is an oracle $A$ such that $\oplus P^A \not\subseteq PP^A$. In fact, there is an oracle $A$ such that $\oplus P^A \not\subseteq PP^{PH^A}$. You can find the result in the following paper.

> Frederic Green, An oracle separating $\oplus P$ from $PP^{PH}$, Information Processing Letters, Volume 37, Issue 3, 18 February 1991, Pages 149-153

> **Comments:**
> **username_0**: Thanks...this is exactly what I was looking for!  In the opening comments to his paper, Green credits Jacobo Torán's Ph.D. thesis with the first oracle $A$ such that $\oplus P^A \not\subseteq PP^A$. This result was subsequently published as Theorem 5.13 in Torán's paper "Complexity classes defined by counting quantifiers," JACM 38 (1991), 752–773.  

---

### Answer by username_3 on 2013-03-24. Score: 16

Scott Aaronson gives an oracle where $\oplus$P = PEXP which implies the oracle you want. <http://eccc.hpi-web.de/report/2005/040/download/> (Theorem 12 in the appendix)

> **Comments:**
> **username_0**: Thanks.  I have to choose just one answer to accept so I'm choosing username_6's answer because it's an earlier reference.  

---

### Answer by username_4 on 2024-05-30. Score: 2

It says that $\oplus P \subseteq PP$ on page 293 in chapter "A Rogues' Gallery of Complexity Classes" of "The Complexity Theory Companion". However, they do not provide a reference to it. You can see the snapshot of the said page below.

[![enter image description here](https://i.sstatic.net/50cEOVHO.png)](https://i.sstatic.net/50cEOVHO.png)

However, it also says that there are oracles relative to which $\oplus P \not\subseteq PP$ on page 259 in chapter "Polynomial Techniques" in section "9.4 OPEN ISSUE: Is PP Closed Under
Polynomial-Time Turing Reductions? " of the same book. Once again, without any reference. You can see the snap shot below.
[![enter image description here](https://i.sstatic.net/WxXG5ifw.png)](https://i.sstatic.net/WxXG5ifw.png)

> **Comments:**
> **username_0**: Thanks for this information! But I'm not sure I believe the assertion here that $\oplus P \subseteq PP$. If it's really a theorem then I would expect it to be a significant result with a citable reference.  
> **username_4**: @TimothyChow I did check the errata of it, which can be found here https://www.cs.rochester.edu/u/lane/=companion/ and did not see it being mentioned over there. So I am not quite sure either. Ok  
> **username_5**: This is most certainly a typo. Besides the lack of references, they surely would not write “$\oplus\mathrm P$ is included in $\mathrm{P^{PP}}$” and mention it as somehow relevant to the PP vs. $\mathrm{P^{PP}}$ problem if they actually thought that $\oplus\mathrm{P\subseteq PP}$ has been proven. You should email them so that they can include it in the errata.  
> **username_5**: I also have serious doubts about “Fact 7”. Neither inclusion seems to follow from anything I saw in Chapter 4, including the notes at the end, and taken together (using also that relativized BPP is low for itself) they would imply $\mathrm{BPP^{PP}=P^{PP}}$, which I strongly suspect to be an open problem.  

---

