Arthur–Merlinプロトコル

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

概要

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

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

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

その他の複雑性クラスとの関係は、 $\mathbf {BPP} \subseteq \exists \cdot \mathbf {BPP} \subseteq \mathbf {MA} \subseteq \mathbf {AM} =\mathbf {BP} \cdot \mathbf {NP} \subseteq \Pi _{2}^{p}$ であることが知られている^[5]^[6]^[7]。この内、分離( $\mathbf {C} \not \subseteq \mathbf {D}$ を示すこと)は難しく^[8]、逆の包含関係も証明されていない。一方で、AMとBP・NPの関係は、単なる定義の言い換えに留まらない。そもそもBabaiのAM導入の動機は、PとBPPの関係の如くNPを拡張できないかという点にあり、検証者が決定的に振る舞うNPに対して、AMは確率的に振る舞う。

定義

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

対話証明としての定義

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

(完全性 completeness) $x\in L$ ならば、 $\Pr((P,V)(x){\mbox{ accepts}})\geq 2/3$
(健全性 soundness) $x\not \in L$ ならば、 $\forall P^{*}\Pr((P^{*},V)(x){\mbox{ accepts}})\leq 1/3$

AM

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

(完全性 completeness) $x\in L$ ならば、 $\Pr _{r\in \{0,1\}^{q(|x|)}}(\exists w\in \{0,1\}^{p(|x|)}\,M(x,w,r)=1)\geq 2/3$
(健全性 soundness) $x\not \in L$ ならば、 $\Pr _{r\in \{0,1\}^{q(|x|)}}(\forall w\in \{0,1\}^{p(|x|)}\,M(x,w,r)=1)\leq 1/3$

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

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

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

MA

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

(完全性 completeness) $x\in L$ ならば、 $\exists w\in \{0,1\}^{p(|x|)}\,\Pr _{r\in \{0,1\}^{q(|x|)}}(M(x,w,r)=1)\geq 2/3$
(健全性 soundness) $x\not \in L$ ならば、 $\forall w\in \{0,1\}^{p(|x|)}\,\Pr _{r\in \{0,1\}^{q(|x|)}}(M(x,w,r)=1)\leq 1/3$

AMと同様に言い換える。

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

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

定義に関する補足

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

また、健全性の定義は、

$\forall w\in \{0,1\}^{p(|x|)}\,\Pr _{r\in \{0,1\}^{q(|x|)}}(M(x,w,r)=0)\geq 2/3$

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

派生するクラス

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

$\mathbf {co{\text{-}}AM} =\{{\bar {L}}|L\in \mathbf {AM} \}$

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

絶対完全性(perfect completeness)は、確率1で完全性が満たされることであり、これを満たす言語のクラスを $\mathbf {AM} ^{pc}$ と書くことにする。一方、絶対健全性(perfect soundness)は、確率1で健全性が満たされることであり、これを満たす言語のクラスを $\mathbf {AM} _{ps}$ と書くことにする。AM及びAM[poly]は、絶対完全性の条件を課しても不変である。つまり、

$\mathbf {AM} ^{pc}=\mathbf {AM}$ ^[10]
$\mathbf {AM} [{\text{poly}}]^{pc}=\mathbf {AM} [{\text{poly}}]$ ^[11]

が成り立つ。一方で、

$\mathbf {AM} [{\text{poly}}]_{ps}=\mathbf {NP}$ ^[11]

である。

AMに属する問題

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

検証者はランダムに $b\in \{0,1\}$ 、 $\pi \in {S_{n}}$ を選び^[12]、 $\pi (G_{b})$ を証明者に送る。
証明者は、 $\pi (G_{b})=G_{\tilde {b}}$ となるような ${\tilde {b}}\in \{0,1\}$ を検証者に送る。
検証者は、 ${\tilde {b}}=b$ ならば受理し、そうでなければ拒否する。

上記のプロトコルは、IP[const]プロトコルである。2つのグラフが非同型のとき検証者は必ず受理し、同型のときどんな証明者でも検証者は1/2の確率で拒否する。

性質

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

AM[2]=AM[k]=MA[k+1]

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

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

$\mathbf {NP} \cup \mathbf {BPP} \subseteq \mathbf {MA} \subseteq \mathbf {AM} \subseteq {\Pi _{2}^{p}}$

特に、 $\mathbf {AM} \subseteq {\Pi _{2}^{p}}$ は、Schöning (1989)によって定義された、任意のクラス ${\mathcal {C}}$ に対するクラス $\mathbf {BP} \cdot {\mathcal {C}}$ を使うことによって、任意のk≧1に対して

$\mathbf {BP} \cdot \Sigma _{k}^{p}\subseteq \Pi _{k+1}^{p}$
$\mathbf {BP} \cdot \Pi _{k}^{p}\subseteq \Sigma _{k+1}^{p}$

と一般化できる( $\mathbf {AM} \subseteq {\Pi _{2}^{p}}$ はk=1のケース)。従って、 $\mathbf {co{\text{-}}AM} \subseteq \Sigma _{2}^{p}$ である。

MAが $\exists \cdot \mathbf {BPP}$ を包含することは明らかだが、逆は知られていない。MAの場合は、 $x\in L$ ならばあるwが存在して、Pr[M(x,w,r)=1]≧2/3を満たす多項式時間チューリングマシンM(x,w,r)が存在すればよい^[14]。対して、 $\exists \cdot \mathbf {BPP}$ は、 $x\in L$ ならば、あるwが存在して、確率的多項式時間チューリングマシンM(x,w)が受理しなければならない(BPPは、任意の入力に対して高い確率で受理するかあるいは拒否するかが決まっていなければならない)。ここでは、(x,w)が入力であるから、任意のw'についても(意味があるかないかに関わらず)Pr[M(x,w',r)=1]は高いか低いかのどちらかであり、例えば1/2となることはない。

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

$\mathbf {IP} [k]\subseteq \mathbf {AM} [k+2]$

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

IP = AM[poly]
AM = IP[const]

とする。

ゼロ知識対話証明との関係について、Fortnow (1987)が、 $\mathbf {SZK} \subseteq \mathbf {co{\text{-}}AM}$ を示した。さらに、Aiello & Håstad (1991)は、 $\mathbf {SZK} \subseteq \mathbf {AM}$ を示した。2つの結果を合わせると、

$\mathbf {SZK} \subseteq \mathbf {AM} \cap \mathbf {co{\text{-}}AM}$

となる。

多項式階層との関係

Boppana, Håstad & Zachos (1987)は次を示した。

$\mathbf {co{\text{-}}NP} \subseteq \mathbf {AM} \Rightarrow \mathbf {PH} \subseteq \mathbf {AM}$

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

一般化すると、k≧1について $\Pi _{k}^{p}\subseteq \mathbf {BP} \cdot \Sigma _{k}^{p}$ (あるいは $\Sigma _{k}^{p}\subseteq \mathbf {BP} \cdot \Pi _{k}^{p}$ )ならば、 $\mathbf {PH} =\mathbf {BP} \cdot \Sigma _{k}^{p}=\mathbf {BP} \cdot \Pi _{k}^{p}$ である^[16]。

還元

$\mathbf {AM} \cap \mathbf {co{\text{-}}AM}$ は多項式時間チューリング還元(Cook還元)で閉じている^[17]。つまり、

$\leq _{T}^{P}(\mathbf {AM} \cap \mathbf {co{\text{-}}AM} )=\mathbf {AM} \cap \mathbf {co{\text{-}}AM}$