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}$.

  • 5
    $\begingroup$ If $\oplus P$ were included in AM, then PH would collapse to AM = coAM by Toda's theorem. $\endgroup$ 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$ 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

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).


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