<p>In the first bullet, we would need the oracle to answer</p>

<ul>
<li><p>YES, if Arthur’s check succeeds with probability $1$ (assuming the MA protocol has perfect completeness),</p></li>
<li><p>NO, if Arthur’s check succeeds with probability $\le 1/2$.</p></li>
</ul>

<p>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 <em>language</em>, but a coRP <em>promise problem</em>, and the whole argument only shows that $\mathrm{MA}\subseteq\mathrm{NP}^{\mathrm{promiseRP}}$.</p>

CC BY-SA 3.0
2012-07-13T13:32:10.910Z
You did not have to make this answer a community wiki, although the choice was up to you.
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-13T10:13:25.690Z
2012-07-13T10:13:25.690Z
Emil Jeřábek
<p>I haven't been able to find a statement relating $\mathsf{MA}$ and $\mathsf{NP}^\mathsf{RP}$ in the literature; pointers would be appreciated.</p>

<p>I believe they are equal:</p>

<ul>
<li><p>$\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.</p></li>
<li><p>$\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.</p></li>
</ul>

<p>Is this correct?</p>

CC BY-SA 3.0
2012-07-11T23:24:06.480Z
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](http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#existsbpp) and the reference therein ([Fenner, Fortnow, Kurtz, and Li 2003](http://dx.doi.org/10.1016/S0890-5401%2803%2900018-X)).
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-12T14:45:37.977Z
Wow! Thanks very much Tsuyoshi, this is a very subtle point, and indeed my first bullet point is wrong.
Joel
CC BY-SA 3.0
2012-07-12T22:11:16.450Z
@TsuyoshiIto: Make that an answer?
Joshua Grochow
CC BY-SA 3.0
2012-07-12T23:32:32.530Z
@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
CC BY-SA 3.0
2012-07-13T10:50:07.720Z
@TsuyoshiIto: Alright, I expanded it into a cw answer.
Emil Jeřábek
<cc.complexity-theory><oracles>
Is $\mathsf{MA}$ equal to $\mathsf{NP}^\mathsf{RP}$?
Joel
# Is $\mathsf{MA}$ equal to $\mathsf{NP}^\mathsf{RP}$?

(Asked by: username_0 on 2012-07-11)

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?

**Tags:** cc.complexity-theory, oracles

> **Comments:**
> **username_1**: 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](http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#existsbpp) and the reference therein ([Fenner, Fortnow, Kurtz, and Li 2003](http://dx.doi.org/10.1016/S0890-5401%2803%2900018-X)).  
> **username_0**: Wow! Thanks very much Tsuyoshi, this is a very subtle point, and indeed my first bullet point is wrong.  
> **username_2**: @TsuyoshiIto: Make that an answer?  
> **username_1**: @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.  
> **username_3**: @TsuyoshiIto: Alright, I expanded it into a cw answer.  

---

## 1 answers

### Answer by username_3 on 2012-07-13. Score: 10 | Accepted answer

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

> **Comments:**
> **username_1**: You did not have to make this answer a community wiki, although the choice was up to you.  

---

