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
  • 5
    $\begingroup$ If $\oplus P$ were included in AM, then PH would collapse to AM = coAM by Toda's theorem. $\endgroup$ Apr 19, 2016 at 12:10
  • $\begingroup$ @Emil, you can post your comment as an answer so the question becomes answered. $\endgroup$
    – Kaveh
    Apr 20, 2016 at 16:08
  • $\begingroup$ @Kaveh OK, though I have doubts about the level of the question. $\endgroup$ Apr 21, 2016 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, 2016 at 15:23

1 Answer 1

9
$\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$

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