I am trying to understand different interactive proof systems, in particular AM and MA.

Is there a typical problem for the complexity class MA as Graph-NonIsomorphism problem is for AM?

Is there a problem in MA that is not known to be in NP or BPP?

It seems to me that MA is a more natural proof system than AM. Is there a reason that most books discuss AM in detail while merely glossing over MA?

  • $\begingroup$ A little speculative (on motive), but AM has a strong relationship with IP, and hence leads on to PCP theory etc., so perhaps the reason for AM being more favoured is that it is tied in with an area that's produced some results that are fantastic to think and talk about. $\endgroup$ Oct 6, 2012 at 9:20
  • 1
    $\begingroup$ Can you state what MA and AM are, as they are not very well known to those not in complexity (well, me at least), or at least provide a wikipedia link? $\endgroup$ Oct 6, 2012 at 12:01
  • $\begingroup$ MA is the generalization of NP where the verifier is allowed to use bounded error probabilistic algorithms. AM requires the additional constraint that the verifier's set of coins are known in advance to the prover. See en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol $\endgroup$
    – Shitikanth
    Oct 6, 2012 at 12:40
  • 3
    $\begingroup$ See this related MathOverflow question. Another reason AM is studied more is that AM has some very nice connections with approximate counting, while the characterizations of MA that we know are not as nice. $\endgroup$
    – Peter Shor
    Oct 7, 2012 at 0:03
  • 2
    $\begingroup$ To add to the comments made so far, perhaps the lack of interesting things we have to say about MA is related to the lack of interesting things we have to say about P vs BPP. If indeed P were equal to BPP, we would have MA=NP. $\endgroup$
    – Shitikanth
    Oct 8, 2012 at 21:38


Your Answer

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