Arthur–Merlinプロトコル

計算複雑性理論におけるArthur–Merlinプロトコルあるいは、Merlin–Arthurプロトコルは、検証者のコイン投げが公開されているタイプの対話型証明プロトコルである。そのようなプロトコルを持つ言語のクラスとして、AM及びMAがそれぞれ定義され、本項では主にこのクラスについて説明する。Babaiによって導入された。

1. 概要
-----

Arthur–Merlinプロトコルは、ArthurとMerlinがやりとりをして、与えられた問題を解くようなプロトコルである。他の対話証明プロトコルと用語を合わせるため、以降、Arthurを検証者、Merlinを証明者と呼ぶ。検証者は、確率的多項式時間で動く標準的なコンピュータであり、証明者は事実上無限の計算能力を持つオラクルである。ただし、証明者は質問に対し必ずしも正直に答えるわけではなく、検証者は回答をよく吟味しなければならない。このような状況下において、問題の答えが"Yes"ならば検証者が受理する確率が少なくとも2/3あり、答えが"No"ならば受理する確率が高々1/3となるようなプロトコルがArthur–Merlinプロトコルである。

Arthur–Merlinプロトコルの特徴的な点は、検証者の使う乱数は公開と設定される所にある。プロトコルでは、検証者からの「質問」は、自身が動作するために使用する乱数のみを送る。よって、無限の計算能力がある証明者は、回答を受け取った検証者がどのように振る舞うのかを完璧に知ることができる。使うコインを秘密にした対話証明であるIPと対比できるが、能力にほぼ差がないことが知られている。

最初、どちらから情報を渡すかによって区別し、検証者から証明者への通信で始まるプロトコルをAMプロトコル、証明者から検証者への通信で始まるプロトコルをMAプロトコルと呼ぶ。通信がk回のAMプロトコルを持つ言語のクラスをAM[k]で表す。ただし、単にAMと言った場合、定数回moveのAM[const]を表す。また、AM=AM[2]であることが知られているため、AMを2-moveのAMプロトコルを持つ言語のクラスとして扱うこともある。

その他の複雑性クラスとの関係は、 であることが知られている。この内、分離は難しく、逆の包含関係も証明されていない。一方で、AMとBP・NPの関係は、単なる定義の言い換えに留まらない。そもそもBabaiのAM導入の動機は、PとBPPの関係の如くNPを拡張できないかという点にあり、検証者が決定的に振る舞うNPに対して、AMは確率的に振る舞う。

2. 定義
-----

他の確率的な複雑性クラスにも言えることだが、定義に現れる2/3や1/3と言った数字に大きな意味はない。複数回行うことによって、確率増幅が可能であるから1/2より有意に大きいことが重要である。

2.1. 対話証明としての定義
---------------

証明者を無限の計算能力を持つチューリングマシン、検証者を確率的多項式時間チューリングマシンとする。PとVは互いに通信可能であり、P→Vの通信と、V→Pの通信をそれぞれ1-moveと数え、合わせて1ラウンドの対話と呼ぶ。Vは自分の持つランダムテープによって挙動が確率的となるが、このテープをV→Pの通信の際に送る。PとVは同一の入力xに対して、k-moveの通信後、Vが受理したとき、チューリングマシンのペアはxを受理するとする。次の条件を満たすとき、言語Lに対するAM[k]対話プロトコルを構成しているといい、言語LはAM[k]に属する。

ならば、
ならば、

2.2. AM
-------

ある言語Lが複雑性クラスAMに属するとき、次を満たす。ただし、Mは決定的多項式時間チューリングマシン、p、qは多項式を表す。

ならば、
ならば、あるいは、次のようにしてもよい。

ある決定的チューリングマシンが存在し、次を満たす。

答えがYesならば、どんな乱数rを選んでも、証拠wが存在し、少なくとも2/3以上の確率で受理する。
答えがNoならば、どんな乱数r、証拠wでも、1/3以下の確率でしか受理しない。

2.3. MA
-------

ある言語Lが複雑性クラスMAに属するとき、次を満たす。ただし、Mは決定的多項式時間チューリングマシン、p、qは多項式を表す。

ならば、
ならば、AMと同様に言い換える。

ある確率的チューリングマシンが存在し、次を満たす。

答えがYesならば、少なくとも2/3以上の確率で受理する証拠wが存在する。
答えがNoならば、どんな証拠wでも、1/3以下の確率でしか受理しない。

2.4. 定義に関する補足
-------------

AMとMAの違いは、乱数を証明者が知ることができるか否かである。AMの場合、乱数が明らかになってから証拠を探すことができるが、MAの場合は、検証者がどのように動くのか、証明者は知らない状態で、証拠を提示しなければならない。

また、健全性の定義は、

等としても同じことである。

2.5. 派生するクラス
------------

複雑性クラス一般に、補問題のクラスを定義できる。AMもまた、co-AMというクラスを考えることができる。形式的には次のように表される。

AM=co-AMかは知られていないが、2つのクラスは異なっていると予想されている。

絶対完全性は、確率1で完全性が満たされることであり、これを満たす言語のクラスをと書くことにする。一方、絶対健全性は、確率1で健全性が満たされることであり、これを満たす言語のクラスをと書くことにする。AM及びAM[poly]は、絶対完全性の条件を課しても不変である。つまり、

が成り立つ。一方で、

である。

3. AMに属する問題
-----------

グラフ非同型問題は、2つのグラフが与えられたとき、同型でないことを判定する問題である。GNIは、AMに属する。具体的なAMプロトコルを構成するよりも、IP[const]プロトコルを構成した方が分かりやすい。

検証者はランダムに、を選び、を証明者に送る。
証明者は、となるようなを検証者に送る。
検証者は、ならば受理し、そうでなければ拒否する。上記のプロトコルは、IP[const]プロトコルである。2つのグラフが非同型のとき検証者は必ず受理し、同型のときどんな証明者でも検証者は1/2の確率で拒否する。

4. 性質
-----

定数回moveのAM[const]及びMA[const]は、すべてAM[2]に潰れる。つまり、任意の定数k≧2に対して次が成り立つ。

AM[2]=AM[k]=MA[k+1]以上の性質より、定数回moveのAM[const]を単にAM、MA[1]を単にMAと表すことする。

また、周辺のクラスとの関係について次が知られている。

特に、は、Schöningによって定義された、任意のクラスに対するクラスを使うことによって、任意のk≧1に対して

と一般化できる。従って、である。

MAがを包含することは明らかだが、逆は知られていない。MAの場合は、ならばあるwが存在して、Pr[M=1]≧2/3を満たす多項式時間チューリングマシンMが存在すればよい。対して、は、ならば、あるwが存在して、確率的多項式時間チューリングマシンMが受理しなければならない。ここでは、が入力であるから、任意のw'についてもPr[M=1]は高いか低いかのどちらかであり、例えば1/2となることはない。

一方、IPとの関係では、任意のkについて

である。本来の定義上の差違は、公開コインを使うか否かという点であったが、実はほぼ差はなかったと言える。表記に統一性がないが、慣行上定数回の対話証明プロトコルを持つ言語はAM、多項式回の対話証明プロトコルを持つ言語はIPに属するという分け方をする。つまり、

IP = AM[poly]
AM = IP[const]とする。

ゼロ知識対話証明との関係について、Fortnowが、を示した。さらに、Aielloは、を示した。2つの結果を合わせると、

となる。

4.1. 多項式階層との関係
--------------

Boppanaは次を示した。

一般に多項式階層は崩壊しないと考えられているので、co-NPがAMに包含されていないだろうと考えられている。また、別証明としてSchöningも知られている。

一般化すると、k≧1についてならば、である。

4.2. 還元
-------

は多項式時間チューリング還元で閉じている。つまり、

である。

5. 注釈
-----

6. 参考文献
-------

last1=Aiello .
last1=Babai .
last1=Boppana .
last1=Fortnow .
last1=Goldreich .
last1=Goldwasser .
和書.

和書.

last=Schöning .
last=Schöning .
和書.

和書.

last1=Zachos .

7. 外部リンク
--------

[1]
[2]

8. 関連項目
-------

対話型証明系
IP
ゼロ知識証明
PZK, SZK, CZK
乱択アルゴリズム