Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-055 | 10th June 2009 00:00

Arthur and Merlin as Oracles



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