Co-Arthur-Merlin

The complement class of AM: a problem is in coAM if its complement is in AM. Equivalently, coAM is the class of problems for which a “no” answer has an Arthur-Merlin protocol — Arthur sends a random challenge, Merlin responds, and Arthur can verify “no” answers with high probability.

See the complexity zoo entry here.

Known relationships

• $\mathbf{BPP}\subseteq \mathbf{coAM}$: BPP problems have a trivial one-message coAM protocol where Merlin’s message is ignored (Arthur decides alone). Symmetrically, $\mathbf{BPP}\subseteq \mathbf{AM}$.
• $\mathbf{SZK}\subseteq \mathbf{AM}\cap \mathbf{coAM}$: statistical zero-knowledge problems can be argued from both sides with Arthur-Merlin protocols — TODO citation.
• $\mathbf{coNP}\subseteq \mathbf{coAM}$, since $\mathbf{NP}\subseteq \mathbf{AM}$ (by GS86) and taking complements.
• If graph isomorphism is $\mathbf{NP}$-complete, then the polynomial hierarchy collapses to ${\mathbf{\Sigma }}_2^{\mathbf{P}}$. This uses the fact that graph non-isomorphism is in $\mathbf{coAM}$, so if GI were NP-complete then $\mathbf{NP}\subseteq \mathbf{coAM}$, collapsing AM to ${\mathbf{\Sigma }}_2^{\mathbf{P}}$ — TODO citation.

Notable problems

• Graph non-isomorphism: given two graphs $G_0,G_1$, are they non-isomorphic? This is in coAM: Arthur picks a random bit $b$ and a random permutation $\pi$, sends $\pi (G_b)$ to Merlin, and Merlin must identify which original graph it came from. If the graphs are non-isomorphic, Merlin (with unbounded power) can always identify $b$ correctly.