<p>Babai introduced a hierarchy of complexity classes based on public-coin randomized interactive proof systems, so called <em>Arthur-Merlin games</em>. The game is played by powerful but untrustworthy wizard Merlin (the prover), and the king Arthur (the verifier), who might flip coins but otherwise his power is polynomially limited. The players exchange messages in turn, and the goal for Merlin is to convince mistrustful Arthur to accept the input string. </p>

<p>$\mathsf{MA}$ is the set of problems that can be decided by one round Arthur-Merlin games with Merlin plays first. First Merlin sends Arthur the "proof", and then Arthur chooses random coins and  tries to verify the "proof" sent by Merlin.</p>

<p>My question is:</p>

<blockquote>
  <p>Is there an oracle relative to which $\mathsf{MA}$ does not have a complete problem?</p>
</blockquote>

<p>It is very likely this problem has been solved already since analogous results exist for $\mathsf{BPP}$ and $\mathsf{ZPP}$. But I couldn't find any reference for it. </p>

<p>Note that an oracle relative to which $\mathsf{BPP}$ does not have a complete problem can be found in </p>

<ul>
<li>Juris Hartmanis and  Lane Hemachandra, <em>Complexity Classes without Machines: On Complete Languages for UP</em>, Theor. Comput. Sci. 58: 129-142 (1988).</li>
</ul>

<p>Analogous result for $\mathsf{ZPP}$ can be found in </p>

<ul>
<li>Daniel P. Bovet, Pierluigi Crescenzi and Riccardo Silvestri, <em>A Uniform Approach to Define Complexity Classes</em>, Theoretical Computer Science 104(2): 263-283 (1992).</li>
</ul>

<p>But I couldn't find a reference for $\mathsf{RP}$ either. This leads to my "side" question:</p>

<blockquote>
  <p>Is there an oracle relative to which $\mathsf{RP}$ does not have a complete problem?</p>
</blockquote>

<p>I would really appreciate if you can point me to the right papers. </p>

CC BY-SA 2.5
2010-11-18T22:08:19.097Z
"MA is the lowest level of this hierarchy": This is not precise. Classes M and A are lower in the hierarchy.
Sadeq Dousti
CC BY-SA 2.5
2010-11-18T22:12:47.940Z
Bravyi *et al.* (http://arxiv.org/abs/quant-ph/0611021) proved that MA has a **natural** complete problem (Stochastic k-SAT). I'm not sure whether their result relativizes or not.
Sadeq Dousti
CC BY-SA 2.5
2010-11-18T22:17:27.327Z
That's arguable, but I will rephrase my question.
Dai Le
CC BY-SA 2.5
2010-11-18T22:29:09.893Z
@Sadeq Dousti: it is called stoquastic k-SAT problem. The QU stands for quantum.
Alessandro Cosentino
CC BY-SA 2.5
2010-11-18T22:57:15.543Z
Be careful not to confuse a “complete language” and a “complete promise problem.”  The paper by Bravyi et al. which Sadeq mentioned is about an MA-complete _promise problem_.  If you are talking about promise problems, MA^A has a complete problem for any language A (almost by definition), and so do BPP^A, ZPP^A and RP^A.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-18T23:23:18.363Z
@Alessandro: Oops! I made a mistake. Thanks for pointing out.
Sadeq Dousti
CC BY-SA 2.5
2010-11-19T12:28:25.070Z
Another useful (but unrelated) paper: [Relativized Arthur-Merlin  versus Merlin-Arthur Games](http://www.springerlink.com/content/f754175q62310q1t/); see also the [journal version](http://linkinghub.elsevier.com/retrieve/pii/0890540189900229). It discusses relativized AM games, but does not pay attention to the complete problem issue.
Sadeq Dousti
CC BY-SA 2.5
2010-11-19T16:22:22.033Z
@Sadeq: I'm aware of this paper, but, yeah, it's not related. Thanks a lot for your comments!
Dai Le
CC BY-SA 2.5
2010-11-21T23:27:05.937Z
Yet another paper that might be related to your question: Error-bounded probabilistic computations between MA and AM, by Böhler, Glaßer and Meister. They construct an oracle relative to which SBP (a class between MA and AM) and AM do not have many-one complete sets.
Alessandro Cosentino
CC BY-SA 2.5
2010-11-22T06:39:18.230Z
@Alessandro: Thanks! I will have a look at the paper.
Dai Le
CC BY-SA 2.5
2010-11-24T14:13:29.010Z
My uneducated guess (without studying the proof by Hartmanis and Hemachandra very much) is that the proof for BPP by Hartmanis and Hemachandra should at least work for both RP and ZPP.  Is there any obstacle?
Tsuyoshi Ito
<cc.complexity-theory><reference-request><complexity-classes><randomness><relativization>
Oracle relative to which MA does not have a complete problem?
Dai Le
# Oracle relative to which MA does not have a complete problem?

(Asked by: username_0 on 2010-11-18)

Babai introduced a hierarchy of complexity classes based on public-coin randomized interactive proof systems, so called *Arthur-Merlin games*. The game is played by powerful but untrustworthy wizard Merlin (the prover), and the king Arthur (the verifier), who might flip coins but otherwise his power is polynomially limited. The players exchange messages in turn, and the goal for Merlin is to convince mistrustful Arthur to accept the input string.

$\mathsf{MA}$ is the set of problems that can be decided by one round Arthur-Merlin games with Merlin plays first. First Merlin sends Arthur the "proof", and then Arthur chooses random coins and tries to verify the "proof" sent by Merlin.

My question is:

> Is there an oracle relative to which $\mathsf{MA}$ does not have a complete problem?

It is very likely this problem has been solved already since analogous results exist for $\mathsf{BPP}$ and $\mathsf{ZPP}$. But I couldn't find any reference for it.

Note that an oracle relative to which $\mathsf{BPP}$ does not have a complete problem can be found in

* Juris Hartmanis and Lane Hemachandra, *Complexity Classes without Machines: On Complete Languages for UP*, Theor. Comput. Sci. 58: 129-142 (1988).

Analogous result for $\mathsf{ZPP}$ can be found in

* Daniel P. Bovet, Pierluigi Crescenzi and Riccardo Silvestri, *A Uniform Approach to Define Complexity Classes*, Theoretical Computer Science 104(2): 263-283 (1992).

But I couldn't find a reference for $\mathsf{RP}$ either. This leads to my "side" question:

> Is there an oracle relative to which $\mathsf{RP}$ does not have a complete problem?

I would really appreciate if you can point me to the right papers.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, randomness, relativization
> **Comments:**
> **username_1**: "MA is the lowest level of this hierarchy": This is not precise. Classes M and A are lower in the hierarchy.  
> **username_1**: Bravyi *et al.* (http://arxiv.org/abs/quant-ph/0611021) proved that MA has a **natural** complete problem (Stochastic k-SAT). I'm not sure whether their result relativizes or not.  
> **username_0**: That's arguable, but I will rephrase my question.  
> **username_2**: @Sadeq Dousti: it is called stoquastic k-SAT problem. The QU stands for quantum.  
> **username_3**: Be careful not to confuse a “complete language” and a “complete promise problem.”  The paper by Bravyi et al. which Sadeq mentioned is about an MA-complete _promise problem_.  If you are talking about promise problems, MA^A has a complete problem for any language A (almost by definition), and so do BPP^A, ZPP^A and RP^A.  
> **username_1**: @Alessandro: Oops! I made a mistake. Thanks for pointing out.  
> **username_1**: Another useful (but unrelated) paper: [Relativized Arthur-Merlin  versus Merlin-Arthur Games](http://www.springerlink.com/content/f754175q62310q1t/); see also the [journal version](http://linkinghub.elsevier.com/retrieve/pii/0890540189900229). It discusses relativized AM games, but does not pay attention to the complete problem issue.  
> **username_0**: @Sadeq: I'm aware of this paper, but, yeah, it's not related. Thanks a lot for your comments!  
> **username_2**: Yet another paper that might be related to your question: Error-bounded probabilistic computations between MA and AM, by Böhler, Glaßer and Meister. They construct an oracle relative to which SBP (a class between MA and AM) and AM do not have many-one complete sets.  
> **username_0**: @Alessandro: Thanks! I will have a look at the paper.  
> **username_3**: My uneducated guess (without studying the proof by Hartmanis and Hemachandra very much) is that the proof for BPP by Hartmanis and Hemachandra should at least work for both RP and ZPP.  Is there any obstacle?  

---

## 0 answers

