<p>By request, I’ll turn the comment into an answer.</p>

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

<p>$\#\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.</p>

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

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

CC BY-SA 3.0
2016-04-21T13:50:31.480Z
2016-04-21T13:50:31.480Z
Emil Jeřábek
<p>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}$?</p>

<p>The same questions apply to the class $\#\mathsf{P}$.</p>

CC BY-SA 3.0
2016-04-19T12:10:27.520Z
If $\oplus P$ were included in AM, then PH would collapse to AM = coAM by Toda's theorem.
Emil Jeřábek
CC BY-SA 3.0
2016-04-20T16:08:18.313Z
@Emil, you can post your comment as an answer so the question becomes answered.
Kaveh
CC BY-SA 3.0
2016-04-21T13:51:26.487Z
@Kaveh OK, though I have doubts about the level of the question.
Emil Jeřábek
CC BY-SA 3.0
2016-04-21T15:23:18.657Z
@Emil, thanks. (I think it is OK, it is not something that would come up in an undergraduate complexity course.)
Kaveh
<cc.complexity-theory><complexity-classes><interactive-proofs>
Parity P and AM
Alexey Milovanov
# Parity P and AM

(Asked by: username_0 on 2016-04-19)

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

**Tags:** cc.complexity-theory, complexity-classes, interactive-proofs
> **Comments:**
> **username_1**: If $\oplus P$ were included in AM, then PH would collapse to AM = coAM by Toda's theorem.  
> **username_2**: @Emil, you can post your comment as an answer so the question becomes answered.  
> **username_1**: @Kaveh OK, though I have doubts about the level of the question.  
> **username_2**: @Emil, thanks. (I think it is OK, it is not something that would come up in an undergraduate complexity course.)  

---

## 1 answers

### Answer by username_1 on 2016-04-21. Score: 9 | Accepted answer

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


---

