ECCC-Report TR09-055https://eccc.weizmann.ac.il/report/2009/055Comments and Revisions published for TR09-055en-usThu, 02 Jul 2009 11:23:31 +0300
Paper TR09-055
| Arthur and Merlin as Oracles |
Venkatesan Chakaravarthy,
Sambuddha Roy
https://eccc.weizmann.ac.il/report/2009/055We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class.
Our main results are the following: (i) $BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii) $S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes $S_2^p$ and $BPP^{NP}_{||}$, these results are interesting from a derandomization perspective. In conjunction with the hitting set generator construction of Miltersan and Vinodchandran [Computational Complexity, 2005], we get that $S_2^p = P^{NP}$ and $BPP^{NP}_{||} = P^{NP}_{||}$, under the hardness hypothesis associated with derandomizing the class $AM$. This gives an alternative proof of the same result obtained by Shaltiel and Umans [Computational Complexity, 2007].
We also show that if $NP$ has polynomial size circuits then the polynomial time hierarchy ($PH$) collapses as $PH = P^{prMA}$. Under the same hypothesis, we also derive an $FP^{prMA}$ algorithm for learning circuits for SAT; this improves the $ZPP^{NP}$ algorithm for the same problem by Bshouty et al.[JCSS, 1996].
Finally, we design a $FP^{prAM}$ algorithm for the problem of finding near-optimal strategies for succinctly presented zero-sum games. For the same problem, Fortnow et al. [Computational Complexity, 2008] described a $ZPP^{NP}$ algorithm. One advantage of our $FP^{prAM}$ algorithm is that it can be derandomized using the construction of Miltersen and Vinodchandran yielding a $FP^{NP}$ algorithm, under a hardness hypothesis used for derandomizing $AM$.
Thu, 02 Jul 2009 11:23:31 +0300https://eccc.weizmann.ac.il/report/2009/055