10
$\begingroup$

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?

$\endgroup$
5
  • 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, 2012 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, 2012 at 14:45
  • $\begingroup$ @TsuyoshiIto: Make that an answer? $\endgroup$ Jul 12, 2012 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, 2012 at 23:32
  • 2
    $\begingroup$ @TsuyoshiIto: Alright, I expanded it into a cw answer. $\endgroup$ Jul 13, 2012 at 10:50

1 Answer 1

10
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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