Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-144 | 8th October 2013 12:48

The two queries assumption and Arthur-Merlin classes


Authors: VyasRam Selvam
Publication: 19th October 2013 12:39
Downloads: 9895


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