アーサー・マーリンプロトコル

計算複雑性理論において、Babai (1985)によって導入されたアーサー・マーリン・プロトコルは、検証者のコイン投げが公開される（つまり証明者にも知られている）ように制約された対話型証明システムである。Goldwasser & Sipser (1986) は、プライベートコインを用いた任意の長さの対話型証明を持つすべての（形式）言語は、公開コインを用いた対話型証明も持つことを証明した。

プロトコルにはアーサーとマーリンという2人の参加者がいるとします。基本的な前提として、アーサーは乱数生成装置を備えた標準的なコンピュータ（または検証装置）であり、マーリンは実質的に無限の計算能力を持つオラクル（証明装置とも呼ばれる）であるとします。しかし、マーリンは必ずしも正直ではないため、アーサーはマーリンがアーサーの質問に対して提供する情報を分析し、問題自体を決定しなければなりません。このプロトコルで解決可能な問題は、答えが「はい」の場合、マーリンがアーサーが少なくとも2/3の確率で受け入れるような一連の応答を持ち、答えが「いいえ」の場合、アーサーが1/3を超える確率で受け入れない場合です。したがって、アーサーは、決定と質問を行うために多項式時間が割り当てられていると仮定すると、確率的多項式時間検証装置として機能します。

このようなプロトコルの中で最も単純なものは、1メッセージプロトコルです。マーリンがアーサーにメッセージを送信し、アーサーは確率的多項式時間計算を実行して、それを受け入れるかどうかを決定します。（これは検証者ベースのNPの定義に似ていますが、唯一の違いは、アーサーがここではランダム性を使用することが許されている点です。）このプロトコルは単一メッセージプロトコルであり、アーサーはマーリンのメッセージを受け取った後にのみコインを投げるため、マーリンはアーサーのコイン投げにアクセスできません。このプロトコルはMAと呼ばれます。非公式には、言語LがMAに含まれるとは、その言語に含まれるすべての文字列に対して、マーリンがアーサーに送って高い確率でこの事実を納得させることができる多項式サイズの証明が存在し、その言語に含まれないすべての文字列に対して、アーサーを高い確率で納得させる証明が存在しないことを意味します。

形式的には、複雑性クラスMAは、アーサーによる計算の前にマーリンの唯一の操作が行われるアーサー-マーリン プロトコルによって多項式時間で決定できる決定問題の集合です。言い換えれば、言語LがMAに含まれるのは、多項式時間決定性チューリング マシンMと多項式p、qが存在し、長さn = | x | のすべての入力文字列xに対して、

• xがLに含まれる場合、${\displaystyle \exists z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\geq 2/3,}$
• xがLに含まれていない場合、${\displaystyle \forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=0)\geq 2/3.}$

2番目の条件は、別の言い方をすれば次のように表すこともできます。

• xがLに含まれていない場合、${\displaystyle \forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\leq 1/3.}$

これを上記の非公式な定義と比較すると、zはマーリンによる証明（そのサイズは多項式で制限される）であり、yはアーサーが使用するランダムな文字列であり、これも多項式で制限される。

複雑性クラスAM (またはAM[2] ) は、2 つのメッセージを持つ Arthur – Merlin プロトコルによって多項式時間で決定できる決定問題の集合です。クエリ/レスポンスのペアは 1 つだけです。Arthur はランダムにコインを投げ、すべてのコイン投げの結果を Merlin に送信します。Merlin は証明と思われるものを返信し、Arthur は決定論的に証明を検証します。このプロトコルでは、Arthur はコイン投げの結果のみを Merlin に送信することが許可されており、最終段階では、Arthur は以前に生成したランダムなコイン投げと Merlin のメッセージのみを使用して、受け入れるか拒否するかを決定しなければなりません。

言い換えれば、言語LがAMに含まれるのは、多項式時間決定性チューリング マシンMと多項式p、qが存在し、長さn = | x | のすべての入力文字列xに対して、

• xがLに含まれる場合、${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\geq 2/3,}$
• xがLに含まれていない場合、${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=0)\geq 2/3.}$

ここでの2番目の条件は次のように書き換えることができます。

• xがLに含まれていない場合、${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 1/3.}$

上記のように、zはマーリンによる証明とされるもの（そのサイズは多項式で制限される）であり、yはアーサーが使用するランダムな文字列であり、これも多項式で制限される。

複雑性クラスAM[ k ]は、 k 個のクエリと応答で多項式時間で解決できる問題の集合です。上記で定義したAMはAM[2]です。AM [3]は、マーリンからアーサーへのメッセージが 1 つ始まり、次にアーサーからマーリンへのメッセージが 1 つ、最後にマーリンからアーサーへのメッセージが 1 つ続きます。アーサーが回答を決定した後にマーリンにメッセージを送信しても何の役にも立たないため、最後のメッセージは常にマーリンからアーサーへのメッセージである必要があります。

• MAとAMは、定義を完全性を要求するように変更しても変化しない。つまり、xが言語に含まれる場合、アーサーは確率1（2/3ではなく）で受理する。^{[ 1 ]}
• 任意の定数k ≥ 2 に対して、クラスAM[ k ]はAM[2]と等しくなります。kが入力サイズと多項式関係にある場合、クラスAM [poly( n )] はクラス IP と等しくなります。クラス IPはPSPACEと等しくなることが知られており、クラスAM[2]よりも強力であると広く考えられています。
• MAはAMに含まれている。なぜならAM [3]にはMAが含まれているからである。アーサーは、マーリンの証明書を受け取った後、必要な数のコインを投げ、それをマーリンに送り、応答を無視することができる。
• AMとMAが異なるかどうかは未解決である。妥当な回路下限（P = BPPを意味するものと同様）の下では、両者ともNPに等しい。^{[ 2 ]}
• AM は、 BP が有界誤差確率演算子を表すクラスBP⋅NPと同じです。また、$\displaystyle \exists \cdot {\mathsf {BPP}}}$( ExistsBPPとも表記) はMAの部分集合です。MAが等しいかどうか$\displaystyle \exists \cdot {\mathsf {BPP}}}$それは未解決の問題である。
• マーリンがアーサーのランダムな決定の結果を予測できないプライベートコインプロトコルへの変換は、一般的にはインタラクションのラウンド数を最大で2回増加させる。したがって、プライベートコイン版のAMはパブリックコイン版と同等である。
• MAはNPとBPPの両方を含んでいます。BPPの場合、アーサーはマーリンを無視して問題を直接解決できるため、これは容易です。NPの場合、マーリンはアーサーに証明書を送信するだけでよく、アーサーはその証明書を多項式時間で決定論的に検証できます。
• MAとAMは_どちらも多項式階層に含まれています。特に、MAはΣ ₂ ^PとΠ ₂ ^Pの交差に含まれ、AMはΠ ₂ ^Pに含まれています。さらに、MAは「対称交代」を表す複雑性クラスで^あるサブクラスSP ² [ ^{3 ]}に含まれています。これはSipser–Lautemannの定理の一般化です。
• AMはNP/polyに含まれます。NP/polyは、多項式サイズの助言を伴う非決定性多項式時間で計算可能な決定問題のクラスです。証明は、アデルマンの定理の変形です。
• MAはPPに含まれている。この結果はVereshchaginによるものである。^{[ 4 ]}
• MAは量子版であるQMAに含まれている。^{[ 5 ]}
• AMには、2つのグラフが同型でないかどうかを判定する問題が含まれています。プライベートコインを使用したプロトコルは次のとおりで、パブリックコインプロトコルに変換できます。2つのグラフGとHが与えられたとき、アーサーはランダムにどちらか一方を選択し、その頂点のランダムな順列を選択して、順列化されたグラフIをマーリンに提示します。マーリンは、IがGまたはHから作成されたかどうかを答える必要があります。グラフが同型でない場合、マーリンは（ IがGと同型であるかどうかを確認することで）完全に確実に答えることができます。しかし、グラフが同型の場合、Iの作成にGまたはHが使用された可能性があり、どちらも同じ確率です。この場合、マーリンはそれらを区別する方法がなく、最大で1/2の確率でアーサーを納得させることができ、これは繰り返しによって1/4に増幅できます。これは実際にはゼロ知識証明です。
• AMがcoNPを含む場合、 PH = AMとなる。これは、グラフ同型性がNP完全である可能性が低いことを示す証拠である。なぜなら、それは多項式階層の崩壊を意味するからである。
• ERHを仮定すると、任意のdに対して「多変数多項式の集合が与えられたとき、${\displaystyle f_{i}}$それぞれが整数係数で次数が最大dであるとき、それらは共通の複素零点を持つか？]はAMに属する。^{[ 6 ]}

• Babai, László (1985)、「群論とランダム性のトレードオフ」、STOC '85: 第17回ACM理論計算機科学シンポジウム議事録、ACM、pp. 421–429、ISBN  978-0-89791-151-1。
• Goldwasser, Shafi ; Sipser, Michael (1986)、「対話型証明システムにおけるプライベートコインとパブリックコイン」、STOC '86: 第18回ACM理論計算シンポジウム議事録、ACM、pp. 59–68、ISBN  978-0-89791-193-1。
• Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge , ISBN 978-0-521-42426-4。
• マドゥ・スーダンによるMITの高度な複雑性に関する講義

• 複雑性動物園：MA
• 複雑性動物園：午前