Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR13-144 | 8th October 2013 12:48

The two queries assumption and Arthur-Merlin classes

TR13-144
Authors: VyasRam Selvam
Publication: 19th October 2013 12:39
Keywords:

Abstract:

We explore the implications of the two queries assumption, \$P^{NP[1]}=P_{||}^{NP[2]}\$, with respect to the polynomial hierarchy and the classes \$AM\$ and \$MA\$.
We prove the following results:

1. \$P^{NP[1]}=P_{||}^{NP[2]}\$ \$\implies\$ \$AM = MA\$
2. \$P^{NP[1]}=P_{||}^{NP[2]}\$ \$\implies\$ \$PH \subset MA_{/1}\$
3. \$\exists\;B\;P^{NP[1]^B}=P^{NP[2]^B}\$ and \$NP^B \not\subseteq coMA^B\$.
4. \$P^{NP[1]}=P_{||}^{NP[2]}\$ \$\implies\$ \$PH = P_{||}^{NP[1],MA[1]} = P_{||}^{NP[2],pr_{coNP}(MA \cap coMA)[1]}\$ (here \$pr_{coNP}(MA \cap coMA)\$ refers to the promise class \$pr(MA \cap coMA)\$ where the
promise is restricted to a \$coNP\$ set)

Under the two queries assumption, the best containment of \$PH\$ known so far in a non-uniform class is \$NP_{/poly}\$ as shown by Kadin. Our result showing the containment of \$PH\$ in \$MA_{/1}\$ betters this.

We also show that the question of whether \$PH\$ collapses to \$AM=MA\$ under the two queries assumption is non-relativizable by constructing an oracle \$B\$ such that \$P^{NP[1]^B}=P^{NP[2]^B}\$ and \$NP^B \not\subseteq coMA^B\$.
This improves upon the result by Buhrman and Fortnow where they showed that the question of whether \$PH\$ collapses to \$NP\$ under the two queries assumption is not relativizable.

Two incomparable results are known regarding the collapse of \$PH\$ under the two queries assumption: the collapse to \$ZPP^{NP[1]}_{1/2-1/exp}\$ shown by Chang and Purini
and the collapse to \$YO^{p}_{2} \cap NO^{p}_{2}\$ shown by Chakaravarthy and Roy.
Our results showing the collapse of \$PH\$ to \$P_{||}^{NP[1],MA[1]}\$ and \$P_{||}^{NP[2],pr_{coNP}(MA \cap coMA)[1]}\$ are incomparable to these.
These results also imply that a collapse of \$PH\$ to \$P^{NP[1]}\$ is possible if and only if \$MA \subseteq P^{NP[1]}\$ or \$pr_{coNP}(MA \cap coMA) \subseteq pr_{coNP}P^{NP[1]}\$ under the two queries assumption.

ISSN 1433-8092 | Imprint