Arthur–Merlinプロトコル
A M ∩ c o - A M {\displaystyle \mathbf {AM} \cap \mathbf {co{\text{-}}AM} } は多項式時間チューリング還元(Cook還元)で閉じている。つまり、
≤ T P ( A M ∩ c o - A M ) = A M ∩ c o - A M {\displaystyle \leq _{T}^{P}(\mathbf {AM} \cap \mathbf {co{\text{-}}AM} )=\mathbf {AM} \cap \mathbf {co{\text{-}}AM} }
である。
Arthur–Merlinプロトコルは、ArthurとMerlinがやりとりをして、与えられた問題を解く(受理する/拒否する)ようなプロトコルである。他の対話証明プロトコルと用語を合わせるため、以降、Arthurを検証者(Verifier)、Merlinを証明者(Prover)と呼ぶ。検証者は、確率的多項式時間で動く標準的なコンピュータであり、証明者は事実上無限の計算能力を持つオラクルである。ただし、証明者は質問に対し必ずしも正直に答えるわけではなく、検証者は回答をよく吟味しなければならない。このような状況下において、問題の答えが"Yes"ならば検証者が受理する確率が少なくとも2/3あり、答えが"No"ならば受理する確率が高々1/3となるようなプロトコルがArthur–Merlinプロトコルである。
Arthur–Merlinプロトコルの特徴的な点は、検証者の使う乱数(コイン)は公開と設定される所にある。プロトコルでは、検証者からの「質問(クエリ)」は、自身が動作するために使用する乱数のみを送る。よって、無限の計算能力がある証明者は、回答を受け取った検証者がどのように振る舞うのかを完璧に知ることができる。使うコインを秘密にした対話証明であるIPと対比できるが、能力にほぼ差がないことが知られている。
最初、どちらから情報を渡すかによって区別し、検証者から証明者への通信で始まるプロトコルをAMプロトコル、証明者から検証者への通信で始まるプロトコルをMAプロトコルと呼ぶ。