Arthur–Merlinプロトコル
ここでは、(x,w)が入力であるから、任意のw'についても(意味があるかないかに関わらず)Pr[M(x,w',r)=1]は高いか低いかのどちらかであり、例えば1/2となることはない。
一方、IPとの関係では、任意のkについて
I P [ k ] ⊆ A M [ k + 2 ] {\displaystyle \mathbf {IP} [k]\subseteq \mathbf {AM} [k+2]}
である。本来の定義上の差違は、公開コインを使うか否かという点であったが、実はほぼ差はなかったと言える。表記に統一性がないが、慣行上定数回の対話証明プロトコルを持つ言語はAM、多項式回の対話証明プロトコルを持つ言語はIPに属するという分け方をする。つまり、
IP = AM[poly]
AM = IP[const]
とする。
ゼロ知識対話証明との関係について、Fortnow (1987)が、 S Z K ⊆ c o - A M {\displaystyle \mathbf {SZK} \subseteq \mathbf {co{\text{-}}AM} } を示した。さらに、Aiello & Håstad (1991)は、 S Z K ⊆ A M {\displaystyle \mathbf {SZK} \subseteq \mathbf {AM} } を示した。2つの結果を合わせると、
S Z K ⊆ A M ∩ c o - A M {\displaystyle \mathbf {SZK} \subseteq \mathbf {AM} \cap \mathbf {co{\text{-}}AM} }
となる。
AMとMAの違いは、乱数を証明者が知ることができるか否かである。AMの場合、乱数が明らかになってから証拠を探すことができる(もはや証明者から見ると、確率的な挙動をしない)が、MAの場合は、検証者がどのように動くのか、証明者は知らない状態で、証拠を提示しなければならない。
また、健全性の定義は、
∀ w ∈ { 0 , 1 } p ( | x | ) Pr r ∈ { 0 , 1 } q ( | x | ) ( M ( x , w , r ) = 0 ) ≥ 2 / 3 {\displaystyle \forall w\in \{0,1\}^{p(|x|)}\,\Pr _{r\in \{0,1\}^{q(|x|)}}(M(x,w,r)=0)\geq 2/3}
等としても同じことである。