IIIT Hyderabad Publications |
|||||||||
|
The Two Queries Assumption And Arthur-Merlin ClassesAuthors: Vyas Ram S Conference: 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014 2014) Date: 2014-08-25 Report no: IIIT/TR/2014/86 AbstractWe 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]}_{||}\) Under the two queries assumption, Chakaravarthy and Roy showed that PH collapses to \(NO^p_2\) [5]. Since \(NP \subseteq MA \subseteq NO^p_2\) unconditionally, our result on relativizability improves upon the result by Buhrman and Fortnow that we cannot show that PH ⊆ NP using relativizable proof techniques [3]. However, we show a containment of PH in a non-uniform variant of AM where Arthur has one bit of advice. This also improves upon the result by Kadin that PH ⊂ NP /poly [11]. Our fourth result shows that simulating MA in a P SAT[1] machine is as hard as collapsing PH to P SAT[1]. Full paper: pdf Centre for VLSI and Embeded Systems Technology |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |