Arthur–Merlinプロトコル
ある言語Lが複雑性クラスMA(=MA[1])に属するとき、次を満たす。ただし、M(・)は決定的多項式時間チューリングマシン、p(・)、q(・)は多項式を表す。
(完全性 completeness) x ∈ L {\displaystyle x\in L} ならば、 ∃ w ∈ { 0 , 1 } p ( | x | ) Pr r ∈ { 0 , 1 } q ( | x | ) ( M ( x , w , r ) = 1 ) ≥ 2 / 3 {\displaystyle \exists w\in \{0,1\}^{p(|x|)}\,\Pr _{r\in \{0,1\}^{q(|x|)}}(M(x,w,r)=1)\geq 2/3}
(健全性 soundness) x ∉ L {\displaystyle x\not \in L} ならば、 ∀ w ∈ { 0 , 1 } p ( | x | ) Pr r ∈ { 0 , 1 } q ( | x | ) ( M ( x , w , r ) = 1 ) ≤ 1 / 3 {\displaystyle \forall w\in \{0,1\}^{p(|x|)}\,\Pr _{r\in \{0,1\}^{q(|x|)}}(M(x,w,r)=1)\leq 1/3}
AMと同様に言い換える。
ある確率的チューリングマシンが存在し、次を満たす。
答えがYesならば、少なくとも2/3以上の確率で受理する証拠wが存在する。
答えがNoならば、どんな証拠wでも、1/3以下の確率でしか受理しない。
複雑性クラス一般に、補問題のクラスを定義できる。AMもまた、co-AMというクラスを考えることができる。形式的には次のように表される。
c o - A M = { L ̄ | L ∈ A M } {\displaystyle \mathbf {co{\text{-}}AM} =\{{\bar {L}}|L\in \mathbf {AM} \}}
AM=co-AMかは知られていないが、2つのクラスは異なっていると予想されている。
絶対完全性(perfect completeness)は、確率1で完全性が満たされることであり、これを満たす言語のクラスを A M p c {\displaystyle \mathbf {AM} ^{pc}} と書くことにする。