The two queries assumption and Arthur-Merlin classes.
Vyas Ram Selvam · Electronic colloquium on computational complexity · 2013
We explore the implications of the two queries assumption, \(P^{SAT[1]}=P^{SAT[2]}_{||}\), with respect to the polynomial hierarchy (PH) and Arthur-Merlin classes. We prove the following results under the assumption \(P^{SAT[1]}=P^{SAT[2]}_{||}\): 1 AM = MA 2 There exists no relativizable proof for PH ⊆ AM 3 Every problem in PH can be solved by a non-uniform variant of an Arthur-Merlin(AM) protocol where Arthur(the verifier) has access to one bit of advice. 4 \(PH = P^{SAT[1],MA[1]}_{||}\)