6
$\begingroup$

What is known about non-trivial inclusions of $\oplus\mathsf{P}$ in other classes? In particular, is it known whether $\oplus\mathsf{P}$ is contained in $\mathsf{AM}$?

The same questions apply to the class $\#\mathsf{P}$.

$\endgroup$
  • 4
    $\begingroup$ If $\oplus P$ were included in AM, then PH would collapse to AM = coAM by Toda's theorem. $\endgroup$ – Emil Jeřábek Apr 19 '16 at 12:10
  • $\begingroup$ @Emil, you can post your comment as an answer so the question becomes answered. $\endgroup$ – Kaveh Apr 20 '16 at 16:08
  • $\begingroup$ @Kaveh OK, though I have doubts about the level of the question. $\endgroup$ – Emil Jeřábek Apr 21 '16 at 13:51
  • $\begingroup$ @Emil, thanks. (I think it is OK, it is not something that would come up in an undergraduate complexity course.) $\endgroup$ – Kaveh Apr 21 '16 at 15:23
8
$\begingroup$

By request, I’ll turn the comment into an answer.

Toda’s theorem says that $\mathrm{PH\subseteq BP\cdot\oplus P}$. Since $\mathrm{BP\cdot AM=AM}$, this shows the following implication: if $\oplus\mathrm P\subseteq\mathrm{AM}$, then the polynomial hierarchy collapses to $\mathrm{PH=AM=coAM}$. (In fact, the whole $\mathrm{Mod_2PH}$ hierarchy collapses to $\mathrm{AM=coAM}$ under the same assumption.)

$\#\mathrm P$ is a class of functions, not of languages, hence it is meaningless to compare it with AM directly. However, if you consider the closely related class $\mathrm{PP}$ instead, the case is similar to $\oplus\mathrm P$: (another version of) Toda’s theorem says that $\mathrm{PH\subseteq P^{PP}=P^{\#P}}$. Thus, if we had $\mathrm{PP\subseteq AM}$, it would follow that $\mathrm{PH\subseteq P^{AM\cap coAM}=AM\cap coAM}$, so we get the same conclusion.

Mutatis mutandis, the same argument suggests neither $\oplus\mathrm P$ nor $\mathrm{PP}$ is contained in $\mathrm{PH}$ as a whole.

I am not aware of any nontrivial inclusions of $\oplus\mathrm P$ or $\mathrm{\#P}$ in other classes (I suppose $\mathrm{\oplus P\subseteq P^{\#P}\subseteq PSPACE}$ count as trivial; there are also levels of the counting hierarchy, but again they contain the offending classes by definition).

$\endgroup$

protected by Community Apr 29 '16 at 13:30

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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