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$ – Luke Mathieson Oct 6 '12 at 9:20
  • $\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$ – Dave Clarke Oct 6 '12 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 '12 at 12:40
  • 2
    $\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 '12 at 0:03
  • 1
    $\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 '12 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.