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