# Is $\mathsf{MA}$ equal to $\mathsf{NP}^\mathsf{RP}$?

I haven't been able to find a statement relating $\mathsf{MA}$ and $\mathsf{NP}^\mathsf{RP}$ in the literature; pointers would be appreciated.

I believe they are equal:

• $\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP}$: The $\mathsf{NP}$ machine guesses Merlin's string, and the $\mathsf{RP}$ oracle verifies the string as Arthur would.

• $\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA}$: Merlin guesses the accepting computation of the $\mathsf{NP}$ machine, including all calls, as well as the outcomes of these calls, to the $\mathsf{RP}$ oracle. Arthur then verifies that the computation is valid and that all the guessed outcomes of calls to the $\mathsf{RP}$ oracle were correct. He uses amplification and union bounds to bound the overall total probability of error.

Is this correct?

• It depends on how you define these notations, but if you define these complexity classes as classes of languages, your reasoning in the first bullet is flawed. Please see ∃BPP in Complexity Zoo and the reference therein (Fenner, Fortnow, Kurtz, and Li 2003). – Tsuyoshi Ito Jul 11 '12 at 23:24
• Wow! Thanks very much Tsuyoshi, this is a very subtle point, and indeed my first bullet point is wrong. – Joel Jul 12 '12 at 14:45
• @TsuyoshiIto: Make that an answer? – Joshua Grochow Jul 12 '12 at 22:11
• @Joshua: I often post a partial answer as a comment when I would not like to post it as my answer for some reason. Anyone should feel free to repost my comment as an answer if he/she would like to. I do not feel obligated to post something as an answer just because I posted it as a comment. – Tsuyoshi Ito Jul 12 '12 at 23:32
• @TsuyoshiIto: Alright, I expanded it into a cw answer. – Emil Jeřábek Jul 13 '12 at 10:50

• YES, if Arthur’s check succeeds with probability $1$ (assuming the MA protocol has perfect completeness),
• NO, if Arthur’s check succeeds with probability $\le 1/2$.
This sounds like a coRP algorithm, but the catch is that there is no guarantee that one of these two conditions applies for every possible input to the oracle. Thus, the oracle does not compute a coRP language, but a coRP promise problem, and the whole argument only shows that $\mathrm{MA}\subseteq\mathrm{NP}^{\mathrm{promiseRP}}$.