14
$\begingroup$

This question was asked by Jan Pax on the Foundations of Mathematics mailing list. Certainly $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ but I suspect from the answers to this question 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?

$\endgroup$
  • 1
    $\begingroup$ 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 ) $\endgroup$ – Marzio De Biasi Mar 24 '13 at 1:05
  • 1
    $\begingroup$ Thanks, Marzio. I guess I should have been more specific: Is there an oracle $A$ such that $\oplus P^A \not\subseteq PP^A$? $\endgroup$ – Timothy Chow Mar 24 '13 at 2:09
  • 1
    $\begingroup$ 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). $\endgroup$ – Alessandro Cosentino Mar 24 '13 at 14:24
  • $\begingroup$ @AlessandroCosentino Is $PP^{\oplus P}=PP$ and ${\oplus P}^{PP}=PP$? What if $PP\subseteq\oplus P$ were true? $\endgroup$ – T.... Dec 18 '17 at 12:49
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Timothy Chow Mar 24 '13 at 22:20
13
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Thanks. I have to choose just one answer to accept so I'm choosing Robin Kothari's answer because it's an earlier reference. $\endgroup$ – Timothy Chow Mar 24 '13 at 22:21

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.