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}$ — AH91 ($\mathbf{AM}$), For87 ($\mathbf{coAM}$); SV03 give a unified proof via Statistical Difference.
• $\mathbf{coNP}\subseteq \mathbf{coAM}$, since $\mathbf{NP}\subseteq \mathbf{AM}$ and taking complements — folklore.
• If graph isomorphism is $\mathbf{NP}$-complete, then the polynomial hierarchy collapses to ${\mathbf{\Sigma }}_2^{\mathbf{P}}$. This uses the fact that graph isomorphism is in $\mathbf{coAM}$, so if GI were NP-complete then $\mathbf{NP}\subseteq \mathbf{coAM}$, i.e. $\mathbf{coNP}\subseteq \mathbf{AM}$, which collapses the hierarchy — BHZ87; see also BM88.

Notable problems

• Graph non-isomorphism: given two graphs $G_0,G_1$, are they non-isomorphic? This is in $\mathbf{AM}$, so graph isomorphism is in $\mathbf{coAM}$ — BM88. In the private-coin protocol of GMW91, the verifier picks a secret random bit $b$ and a random permutation $\pi$, sends $\pi (G_b)$ to the prover, and the prover must identify which original graph it came from. If the graphs are non-isomorphic, the prover (with unbounded power) can always identify $b$ correctly. The verifier’s coins must stay hidden; GS86 convert such private-coin protocols into Arthur–Merlin protocols.

Participates in

Produces Co-Arthur-Merlin

• BPP ⊆ coAM
• coNP ⊆ coAM
• SZK ⊆ coAM