Arthur–Merlinプロトコル
一方、絶対健全性(perfect soundness)は、確率1で健全性が満たされることであり、これを満たす言語のクラスを A M p s {\displaystyle \mathbf {AM} _{ps}} と書くことにする。AM及びAM[poly]は、絶対完全性の条件を課しても不変である。つまり、
A M p c = A M {\displaystyle \mathbf {AM} ^{pc}=\mathbf {AM} }
A M [ poly ] p c = A M [ poly ] {\displaystyle \mathbf {AM} [{\text{poly}}]^{pc}=\mathbf {AM} [{\text{poly}}]}
が成り立つ。一方で、
A M [ poly ] p s = N P {\displaystyle \mathbf {AM} [{\text{poly}}]_{ps}=\mathbf {NP} }
である。
証明者(Prover, P)を無限の計算能力を持つチューリングマシン、検証者(Verifier, V)を確率的多項式時間チューリングマシンとする。PとVは互いに通信可能であり、P→Vの通信と、V→Pの通信をそれぞれ1-moveと数え、合わせて1ラウンドの対話と呼ぶ。Vは自分の持つランダムテープによって挙動が確率的となるが、このテープをV→Pの通信の際に送る。PとVは同一の入力xに対して、k-moveの通信後、Vが受理(accept)したとき、チューリングマシンのペア(P,V)(x)はxを受理するとする。次の条件を満たすとき、言語Lに対するAM[k](V→Pから始めた場合。P→Vから始めた場合はMA[k])対話プロトコルを構成しているといい、言語LはAM[k](あるいはMA[k])に属する。
(完全性 completeness) x ∈ L {\displaystyle x\in L} ならば、 Pr ( ( P , V ) ( x ) accepts ) ≥ 2 / 3 {\displaystyle \Pr((P,V)(x){\mbox{ accepts}})\geq 2/3}
(健全性 soundness) x ∉ L {\displaystyle x\not \in L} ならば、 ∀ P ∗ Pr ( ( P ∗ , V ) ( x ) accepts ) ≤ 1 / 3 {\displaystyle \forall P^{*}\Pr((P^{*},V)(x){\mbox{ accepts}})\leq 1/3}