ECCC-Report TR13-144https://eccc.weizmann.ac.il/report/2013/144Comments and Revisions published for TR13-144en-usSat, 19 Oct 2013 12:39:42 +0300
Paper TR13-144
| The two queries assumption and Arthur-Merlin classes |
VyasRam Selvam
https://eccc.weizmann.ac.il/report/2013/144We 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.
Sat, 19 Oct 2013 12:39:42 +0300https://eccc.weizmann.ac.il/report/2013/144