対話型証明系
NP をより対話的に定式化することもできるが、そのような対話による計算の概念は1985年になって登場した。それは、László Babai の発表した "Trading group theory for randomness" という論文で定義された Arthur-Merlin(AM)クラス階層によるものである。その中で Arthur(検証者)は確率的多項式時間機械であり、Merlin(証明者)は無限の計算資源を持つ機械である。
クラス MA は、上述の NP の対話の単純な一般化であり、検証者は確率的ではなく決定的である。また、検証者が常に妥当な証拠を受理して妥当でないものを拒絶するのではなく、以下のようにもっと寛大な方針を採用する。
完全性: 文字列が言語に属する場合、証明者は検証者が受理するような証拠を最低でも 2/3 の確率で与えることができる(検証者の無作為選択に依存する)。
健全性: 文字列が言語に属さない場合、悪意の有無に関わらず、証明者が検証者が受理するような証拠を与えることができる確率は 1/3 未満である。
これは、通常のNPの対話プロトコルよりも強力であり、BPPのアルゴリズムが実用的であるように、このような確率的な証拠であっても検証に値する。Babai の提唱した他のクラスについては後述する。