1
$\begingroup$

I just can't figure out the difference between these three classes of complexity, does anyone know the difference and can explain it in a simple, direct way without too many definitions involved? Thank you very much!

$\endgroup$
1
  • $\begingroup$ For those interested in Proof Assistants, there is a new proposed SE site ProofAssistants $\endgroup$
    – Guy Coder
    Nov 28, 2021 at 8:35

1 Answer 1

1
$\begingroup$

All of these classes can be described as consisting of languages accepted by certain Arthur–Merlin games. In these games, Merlin, an unlimited but potentially dishonest party, tries to convince Arthur, a probabilistic Turing machine, that the input $x$ belongs to the language $L$. We ask that if $x \in L$ then some Merlin convinces Arthur with probability at least $2/3$, and if $x \notin L$ then every Merlin convinces Arthur with probability at most $1/3$.

Without any further limitations, we get the class IP (which equals PSPACE). If we only allow a constant number of rounds of interaction, we get the class AM (it is known that without loss of generality, there are only two rounds). If we don't allow any interaction (Merlin gets no chance to speak), then we get BPP.

$\endgroup$
7
  • $\begingroup$ thanks a lot, but, does this mean that Arthur-Merlin games and IP are equivalent then? Since you said that from those and without any limitation we get IP.. but maybe I misunderstood and they are very just similar but used in different contexts? Sorry, english isn't my native language $\endgroup$ Oct 11, 2021 at 21:34
  • $\begingroup$ I've just found out that generally AM games use a public coin mechanism, while IP a private one, is that the only difference? I also read that the nature of the coin isn't that influent, does this make IP and AM games equal? If yes, why we distinct them, then? $\endgroup$ Oct 11, 2021 at 21:52
  • $\begingroup$ AM protocols have two rounds, without loss of generality. IP protocols have polynomially many rounds; the number of rounds could depend on $n$. I suggest ignoring the technical issue of public vs private coins for now. $\endgroup$ Oct 11, 2021 at 21:54
  • $\begingroup$ Also, for some reason you’re equating AM with whatever can be accepted using unrestricted Arthur-Merlin protocols, but that’s just not how AM is defined. $\endgroup$ Oct 11, 2021 at 21:56
  • $\begingroup$ Rather, AM is so named because there is an Arthur round followed by a Merlin round, in contrast to MA, in which the order is reversed. $\endgroup$ Oct 11, 2021 at 22:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.