Arthur–Merlinプロトコル
計算複雑性理論におけるArthur–Merlinプロトコル(Arthur–Merlin protocol)あるいは、Merlin–Arthurプロトコル(Merlin–Arthur protocol)は、検証者のコイン投げが公開されている(使用する乱数が証明者に知られている)タイプの対話型証明プロトコルである。そのようなプロトコルを持つ言語のクラスとして、AM及びMAがそれぞれ定義され、本項では主にこのクラスについて説明する。Babai (1985)によって導入された。
Boppana, Håstad & Zachos (1987)は次を示した。
c o - N P ⊆ A M ⇒ P H ⊆ A M {\displaystyle \mathbf {co{\text{-}}NP} \subseteq \mathbf {AM} \Rightarrow \mathbf {PH} \subseteq \mathbf {AM} }
一般に多項式階層は崩壊しないと考えられているので、co-NPがAMに包含されていないだろうと考えられている。また、別証明としてSchöning (1988)も知られている。
一般化すると、k≧1について Π k p ⊆ B P ⋅ Σ k p {\displaystyle \Pi _{k}^{p}\subseteq \mathbf {BP} \cdot \Sigma _{k}^{p}} (あるいは Σ k p ⊆ B P ⋅ Π k p {\displaystyle \Sigma _{k}^{p}\subseteq \mathbf {BP} \cdot \Pi _{k}^{p}} )ならば、 P H = B P ⋅ Σ k p = B P ⋅ Π k p {\displaystyle \mathbf {PH} =\mathbf {BP} \cdot \Sigma _{k}^{p}=\mathbf {BP} \cdot \Pi _{k}^{p}} である。