TR09-055 Authors: Venkatesan Chakaravarthy, Sambuddha Roy

Publication: 2nd July 2009 11:23

Downloads: 1427

Keywords:

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