REPORTS > DETAIL:

### Paper:

TR09-055 | 10th June 2009 00:00

#### Arthur and Merlin as Oracles

TR09-055
Authors: Venkatesan Chakaravarthy, Sambuddha Roy
Publication: 2nd July 2009 11:23
Keywords:

Abstract:

We 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\$.

ISSN 1433-8092 | Imprint