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.

  • $\begingroup$ "MA is the lowest level of this hierarchy": This is not precise. Classes M and A are lower in the hierarchy. $\endgroup$ Nov 18, 2010 at 22:08
  • 1
    $\begingroup$ @Sadeq Dousti: it is called stoquastic k-SAT problem. The QU stands for quantum. $\endgroup$ Nov 18, 2010 at 22:29
  • 10
    $\begingroup$ 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. $\endgroup$ Nov 18, 2010 at 22:57
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 21, 2010 at 23:27
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 24, 2010 at 14:13


Your Answer

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