Arthur–Merlinプロトコル
グラフ非同型問題(Graph Non-Isomorphism problem, GNI)は、2つのグラフ G 0 , G 1 {\displaystyle G_{0},G_{1}} が与えられたとき、同型でないことを判定する問題である。GNIは、AMに属する。具体的なAMプロトコルを構成するよりも、IP[const]プロトコルを構成した方が分かりやすい。
検証者はランダムに b ∈ { 0 , 1 } {\displaystyle b\in \{0,1\}} 、 π ∈ S n {\displaystyle \pi \in {S_{n}}} を選び、 π ( G b ) {\displaystyle \pi (G_{b})} を証明者に送る。
証明者は、 π ( G b ) = G b ~ {\displaystyle \pi (G_{b})=G_{\tilde {b}}} となるような b ~ ∈ { 0 , 1 } {\displaystyle {\tilde {b}}\in \{0,1\}} を検証者に送る。
検証者は、 b ~ = b {\displaystyle {\tilde {b}}=b} ならば受理し、そうでなければ拒否する。
上記のプロトコルは、IP[const]プロトコルである。2つのグラフが非同型のとき検証者は必ず受理し、同型のときどんな証明者でも検証者は1/2の確率で拒否する。
通信がk回のAMプロトコルを持つ言語のクラス(あるいはMAプロトコルを持つ言語のクラス)をAM[k](あるいはMA[k])で表す。ただし、単にAM(あるいはMA)と言った場合、定数回moveのAM[const](あるいはMA[1])を表す。また、AM=AM[2]であることが知られているため、AMを2-moveのAMプロトコルを持つ言語のクラスとして扱うこともある。
その他の複雑性クラスとの関係は、 B P P ⊆ ∃ ⋅ B P P ⊆ M A ⊆ A M = B P ⋅ N P ⊆ Π 2 p {\displaystyle \mathbf {BPP} \subseteq \exists \cdot \mathbf {BPP} \subseteq \mathbf {MA} \subseteq \mathbf {AM} =\mathbf {BP} \cdot \mathbf {NP} \subseteq \Pi _{2}^{p}} であることが知られている。この内、分離( C ⊈ D {\displaystyle \mathbf {C} \not \subseteq \mathbf {D} } を示すこと)は難しく、逆の包含関係も証明されていない。一方で、AMとBP・NPの関係は、単なる定義の言い換えに留まらない。そもそもBabaiのAM導入の動機は、PとBPPの関係の如くNPを拡張できないかという点にあり、検証者が決定的に振る舞うNPに対して、AMは確率的に振る舞う。