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

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

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

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

形式的には、複雑性クラス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 はMerlin からの証明とされるもの (そのサイズは多項式で制限される) であり、y はArthur が使用するランダムな文字列 (これも多項式で制限される) です。

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

言い換えれば、言語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)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 1/3.}$

上記のように、z はMerlin からの証明とされるもの (そのサイズは多項式で制限されます) であり、y はArthur が使用するランダムな文字列であり、これも多項式で制限されます。

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

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

• ババイ、ラースロー(1985)、「ランダム性のためのトレーディング グループ理論」、STOC '85: 第 17 回 ACM コンピューティング理論シンポジウム議事録、ACM、pp. 421–429、ISBN 978-0-89791-151-1。
• Goldwasser, Shafi ; Sipser, Michael (1986)、「対話型証明システムにおけるプライベートコインとパブリックコイン」、STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing、ACM、pp. 59–68、ISBN 978-0-89791-193-1。
• アローラ、サンジーヴ、バラク、ボアズ（2009）、計算複雑性：現代的アプローチ、ケンブリッジ、ISBN 978-0-521-42426-4。
• マドゥ・スーダンのMITにおける高度な複雑性に関する講座

• 複雑性動物園: MA
• 複雑動物園：AM