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 AM. The main result is that ]> . An important property of the class ]> is that it can be derandomized as ]> , under a natural hardness hypothesis used for derandomizing the class AM; this directly follows from a result due to Miltersen and Vinodchandran [10]. As a consequence, we get that ]> , under the above hypothesis. This gives an alternative (and perhaps, a simpler) proof of the same result obtained by Shaltiel and Umans [16], using different techniques. Next, we present an FP^prAM algorithm for finding near-optimal strategies of a succinctly presented zero-sum game. For the same problem, Fortnow et al. [7] described a ZPP^NP algorithm. As a by product of our algorithm, we also get an alternative proof of the result by Fortnow et. al. One advantage with an FP^prAM algorithm is that it can be directly derandomized using the Miltersen-Vinodchandran construction [10]. As a consequence, we get an FP^NP algorithm for the above problem, under the hardness hypothesis used for derandomizing AM. [ABSTRACT FROM AUTHOR]