__
TR13-144 | 8th October 2013 12:48
__

#### The two queries assumption and Arthur-Merlin classes

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