Arthur–Merlinプロトコル
定数回moveのAM[const]及びMA[const]は、すべてAM[2]に潰れる。つまり、任意の定数k≧2に対して次が成り立つ。
AM[2]=AM[k]=MA[k+1]
以上の性質より、定数回moveのAM[const]を単にAM、MA[1](及びMA[2])を単にMAと表すことする。
また、周辺のクラスとの関係について次が知られている。
N P ∪ B P P ⊆ M A ⊆ A M ⊆ Π 2 p {\displaystyle \mathbf {NP} \cup \mathbf {BPP} \subseteq \mathbf {MA} \subseteq \mathbf {AM} \subseteq {\Pi _{2}^{p}}}
特に、 A M ⊆ Π 2 p {\displaystyle \mathbf {AM} \subseteq {\Pi _{2}^{p}}} は、Schöning (1989)によって定義された、任意のクラス C {\displaystyle {\mathcal {C}}} に対するクラス B P ⋅ C {\displaystyle \mathbf {BP} \cdot {\mathcal {C}}} を使うことによって、任意のk≧1に対して
B P ⋅ Σ k p ⊆ Π k + 1 p {\displaystyle \mathbf {BP} \cdot \Sigma _{k}^{p}\subseteq \Pi _{k+1}^{p}}
ある言語Lが複雑性クラスAM(=AM[2])に属するとき、次を満たす。ただし、M(・)は決定的多項式時間チューリングマシン、p(・)、q(・)は多項式を表す。
(完全性 completeness) x ∈ L {\displaystyle x\in L} ならば、 Pr r ∈ { 0 , 1 } q ( | x | ) ( ∃ w ∈ { 0 , 1 } p ( | x | ) M ( x , w , r ) = 1 ) ≥ 2 / 3 {\displaystyle \Pr _{r\in \{0,1\}^{q(|x|)}}(\exists w\in \{0,1\}^{p(|x|)}\,M(x,w,r)=1)\geq 2/3}
(健全性 soundness) x ∉ L {\displaystyle x\not \in L} ならば、 Pr r ∈ { 0 , 1 } q ( | x | ) ( ∀ w ∈ { 0 , 1 } p ( | x | ) M ( x , w , r ) = 1 ) ≤ 1 / 3 {\displaystyle \Pr _{r\in \{0,1\}^{q(|x|)}}(\forall w\in \{0,1\}^{p(|x|)}\,M(x,w,r)=1)\leq 1/3}
あるいは、次のようにしてもよい。
ある決定的チューリングマシンが存在し、次を満たす。
答えがYesならば、どんな乱数rを選んでも、証拠wが存在し、少なくとも2/3以上の確率で受理する。
答えがNoならば、どんな乱数r、証拠wでも、1/3以下の確率でしか受理しない。
他の確率的な複雑性クラスにも言えることだが、定義に現れる2/3や1/3と言った数字に大きな意味はない。複数回行うことによって、確率増幅が可能であるから1/2より有意に大きい(あるいは小さい)ことが重要である。