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?

  • 6
    $\begingroup$ 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). $\endgroup$ Jul 11 '12 at 23:24
  • $\begingroup$ Wow! Thanks very much Tsuyoshi, this is a very subtle point, and indeed my first bullet point is wrong. $\endgroup$
    – Joel
    Jul 12 '12 at 14:45
  • $\begingroup$ @TsuyoshiIto: Make that an answer? $\endgroup$ Jul 12 '12 at 22:11
  • $\begingroup$ @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. $\endgroup$ Jul 12 '12 at 23:32
  • 2
    $\begingroup$ @TsuyoshiIto: Alright, I expanded it into a cw answer. $\endgroup$ Jul 13 '12 at 10:50

In the first bullet, we would need the oracle to answer

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

  • $\begingroup$ You did not have to make this answer a community wiki, although the choice was up to you. $\endgroup$ Jul 13 '12 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.