Arthur–Merlinプロトコル
↑ 由来は、アーサー王物語のアーサー王とマーリン
↑ つまり、証明者もそれを知ることができる
↑ IP
↑ 例えば、AM[3]は、検証者→証明者、証明者→検証者、検証者→証明者というやりとりをするプロトコルを持つ言語クラス
↑ BPP
↑ NP
↑ Π2
↑ 直ちにP≠NPが導かれる
↑ co-AMはco-NPを包含するので、AM=co-AMならば、 P H ⊆ A M {\displaystyle \mathbf {PH} \subseteq \mathbf {AM} }
↑ Zachos & Furer (1987)
1 2 Goldreich, Mansour & Sipser (1987)
↑ S n {\displaystyle S_{n}} はn次対称群
1 2 Babai (1985)
↑ ここで、証明者から与えられるw以外について、例えばw'についてPr[M(x,w',r)=1]がどうなるか何も条件を課しておらず、1/2となってもよいことに注意
↑ Goldwasser & Sipser (1986)
↑ Schöning (1989)
↑ 戸田 (2001, p. 28)
B P ⋅ Π k p ⊆ Σ k + 1 p {\displaystyle \mathbf {BP} \cdot \Pi _{k}^{p}\subseteq \Sigma _{k+1}^{p}}
と一般化できる( A M ⊆ Π 2 p {\displaystyle \mathbf {AM} \subseteq {\Pi _{2}^{p}}} はk=1のケース)。従って、 c o - A M ⊆ Σ 2 p {\displaystyle \mathbf {co{\text{-}}AM} \subseteq \Sigma _{2}^{p}} である。
MAが ∃ ⋅ B P P {\displaystyle \exists \cdot \mathbf {BPP} } を包含することは明らかだが、逆は知られていない。MAの場合は、 x ∈ L {\displaystyle x\in L} ならばあるwが存在して、Pr[M(x,w,r)=1]≧2/3を満たす多項式時間チューリングマシンM(x,w,r)が存在すればよい。対して、 ∃ ⋅ B P P {\displaystyle \exists \cdot \mathbf {BPP} } は、 x ∈ L {\displaystyle x\in L} ならば、あるwが存在して、確率的多項式時間チューリングマシンM(x,w)が受理しなければならない(BPPは、任意の入力に対して高い確率で受理するかあるいは拒否するかが決まっていなければならない)。