計算複雑性理論 における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 プロトコルを持つ言語のクラスとして扱うこともある。
その他の複雑性クラスとの関係は、
B
P
P
⊆
∃
⋅
B
P
P
⊆
M
A
⊆
A
M
=
B
P
⋅
N
P
⊆
Π
2
p
{\displaystyle \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]
C
⊈
D
{\displaystyle \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
∈
L
{\displaystyle x\in L}
Pr
(
(
P
,
V
)
(
x
)
accepts
)
≥
2
/
3
{\displaystyle \Pr((P,V)(x){\mbox{ accepts}})\geq 2/3}
(健全性 soundness )
x
∉
L
{\displaystyle x\not \in L}
∀
P
∗
Pr
(
(
P
∗
,
V
)
(
x
)
accepts
)
≤
1
/
3
{\displaystyle \forall P^{*}\Pr((P^{*},V)(x){\mbox{ accepts}})\leq 1/3}
AM
ある言語Lが複雑性クラスAM (=AM [2])に属するとき、次を満たす。ただし、M(・)は決定的多項式時間チューリングマシン、p(・)、q(・)は多項式を表す。
(完全性 completeness )
x
∈
L
{\displaystyle x\in L}
Pr
r
∈
{
0
,
1
}
q
(
|
x
|
)
(
∃
w
∈
{
0
,
1
}
p
(
|
x
|
)
M
(
x
,
w
,
r
)
=
1
)
≥
2
/
3
{\displaystyle \Pr _{r\in \{0,1\}^{q(|x|)}}(\exists w\in \{0,1\}^{p(|x|)}\,M(x,w,r)=1)\geq 2/3}
(健全性 soundness )
x
∉
L
{\displaystyle x\not \in L}
Pr
r
∈
{
0
,
1
}
q
(
|
x
|
)
(
∀
w
∈
{
0
,
1
}
p
(
|
x
|
)
M
(
x
,
w
,
r
)
=
1
)
≤
1
/
3
{\displaystyle \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
∈
L
{\displaystyle x\in L}
∃
w
∈
{
0
,
1
}
p
(
|
x
|
)
Pr
r
∈
{
0
,
1
}
q
(
|
x
|
)
(
M
(
x
,
w
,
r
)
=
1
)
≥
2
/
3
{\displaystyle \exists w\in \{0,1\}^{p(|x|)}\,\Pr _{r\in \{0,1\}^{q(|x|)}}(M(x,w,r)=1)\geq 2/3}
(健全性 soundness )
x
∉
L
{\displaystyle x\not \in L}
∀
w
∈
{
0
,
1
}
p
(
|
x
|
)
Pr
r
∈
{
0
,
1
}
q
(
|
x
|
)
(
M
(
x
,
w
,
r
)
=
1
)
≤
1
/
3
{\displaystyle \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 の場合は、検証者がどのように動くのか、証明者は知らない状態で、証拠を提示しなければならない。
また、健全性の定義は、
∀
w
∈
{
0
,
1
}
p
(
|
x
|
)
Pr
r
∈
{
0
,
1
}
q
(
|
x
|
)
(
M
(
x
,
w
,
r
)
=
0
)
≥
2
/
3
{\displaystyle \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 というクラスを考えることができる。形式的には次のように表される。
c
o
-
A
M
=
{
L
¯
|
L
∈
A
M
}
{\displaystyle \mathbf {co{\text{-}}AM} =\{{\bar {L}}|L\in \mathbf {AM} \}}
AM =co-AM かは知られていないが、2つのクラスは異なっていると予想されている[ 9]
絶対完全性 (perfect completeness )は、確率1で完全性が満たされることであり、これを満たす言語のクラスを
A
M
p
c
{\displaystyle \mathbf {AM} ^{pc}}
絶対健全性 (perfect soundness )は、確率1で健全性が満たされることであり、これを満たす言語のクラスを
A
M
p
s
{\displaystyle \mathbf {AM} _{ps}}
AM 及びAM [poly]は、絶対完全性の条件を課しても不変である。つまり、
A
M
p
c
=
A
M
{\displaystyle \mathbf {AM} ^{pc}=\mathbf {AM} }
[ 10]
A
M
[
poly
]
p
c
=
A
M
[
poly
]
{\displaystyle \mathbf {AM} [{\text{poly}}]^{pc}=\mathbf {AM} [{\text{poly}}]}
[ 11] が成り立つ。一方で、
A
M
[
poly
]
p
s
=
N
P
{\displaystyle \mathbf {AM} [{\text{poly}}]_{ps}=\mathbf {NP} }
[ 11] である。
グラフ非同型問題 (Graph Non-Isomorphism problem, GNI)は、2つのグラフ
G
0
,
G
1
{\displaystyle G_{0},G_{1}}
同型 でないことを判定する問題である。GNIは、AM に属する。具体的なAM プロトコルを構成するよりも、IP [const]プロトコルを構成した方が分かりやすい。
検証者はランダムに
b
∈
{
0
,
1
}
{\displaystyle b\in \{0,1\}}
π
∈
S
n
{\displaystyle \pi \in {S_{n}}}
[ 12]
π
(
G
b
)
{\displaystyle \pi (G_{b})}
証明者は、
π
(
G
b
)
=
G
b
~
{\displaystyle \pi (G_{b})=G_{\tilde {b}}}
b
~
∈
{
0
,
1
}
{\displaystyle {\tilde {b}}\in \{0,1\}}
検証者は、
b
~
=
b
{\displaystyle {\tilde {b}}=b}
上記のプロトコルは、IP [const]プロトコルである。2つのグラフが非同型のとき検証者は必ず受理し、同型のときどんな証明者でも検証者は1/2の確率で拒否する。
定数回moveのAM [const]及びMA [const]は、すべてAM[2]に潰れる。つまり、任意の定数k≧2に対して次が成り立つ[ 13]
以上の性質より、定数回moveのAM [const]を単にAM 、MA [1](及びMA [2])を単にMA と表すことする。
また、周辺のクラスとの関係について次が知られている[ 13]
N
P
∪
B
P
P
⊆
M
A
⊆
A
M
⊆
Π
2
p
{\displaystyle \mathbf {NP} \cup \mathbf {BPP} \subseteq \mathbf {MA} \subseteq \mathbf {AM} \subseteq {\Pi _{2}^{p}}}
特に、
A
M
⊆
Π
2
p
{\displaystyle \mathbf {AM} \subseteq {\Pi _{2}^{p}}}
Schöning (1989) によって定義された、任意のクラス
C
{\displaystyle {\mathcal {C}}}
B
P
⋅
C
{\displaystyle \mathbf {BP} \cdot {\mathcal {C}}}
B
P
⋅
Σ
k
p
⊆
Π
k
+
1
p
{\displaystyle \mathbf {BP} \cdot \Sigma _{k}^{p}\subseteq \Pi _{k+1}^{p}}
B
P
⋅
Π
k
p
⊆
Σ
k
+
1
p
{\displaystyle \mathbf {BP} \cdot \Pi _{k}^{p}\subseteq \Sigma _{k+1}^{p}}
と一般化できる(
A
M
⊆
Π
2
p
{\displaystyle \mathbf {AM} \subseteq {\Pi _{2}^{p}}}
c
o
-
A
M
⊆
Σ
2
p
{\displaystyle \mathbf {co{\text{-}}AM} \subseteq \Sigma _{2}^{p}}
MA が
∃
⋅
B
P
P
{\displaystyle \exists \cdot \mathbf {BPP} }
MA の場合は、
x
∈
L
{\displaystyle x\in L}
[ 14]
∃
⋅
B
P
P
{\displaystyle \exists \cdot \mathbf {BPP} }
x
∈
L
{\displaystyle x\in L}
BPP は、任意の入力 に対して高い確率で受理するかあるいは拒否するかが決まっていなければならない)。ここでは、(x,w)が入力であるから、任意のw'についても(意味があるかないかに関わらず)Pr[M(x,w',r)=1]は高いか低いかのどちらかであり、例えば1/2となることはない。
一方、IP との関係では、任意のkについて
I
P
[
k
]
⊆
A
M
[
k
+
2
]
{\displaystyle \mathbf {IP} [k]\subseteq \mathbf {AM} [k+2]}
である[ 15] AM 、多項式回の対話証明プロトコルを持つ言語はIP に属するという分け方をする。つまり、
IP = AM [poly]AM = IP [const]とする。
ゼロ知識対話証明との関係について、Fortnow (1987) が、
S
Z
K
⊆
c
o
-
A
M
{\displaystyle \mathbf {SZK} \subseteq \mathbf {co{\text{-}}AM} }
Aiello & Håstad (1991) は、
S
Z
K
⊆
A
M
{\displaystyle \mathbf {SZK} \subseteq \mathbf {AM} }
S
Z
K
⊆
A
M
∩
c
o
-
A
M
{\displaystyle \mathbf {SZK} \subseteq \mathbf {AM} \cap \mathbf {co{\text{-}}AM} }
となる。
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}}
[ 16]
A
M
∩
c
o
-
A
M
{\displaystyle \mathbf {AM} \cap \mathbf {co{\text{-}}AM} }
[ 17]
≤
T
P
(
A
M
∩
c
o
-
A
M
)
=
A
M
∩
c
o
-
A
M
{\displaystyle \leq _{T}^{P}(\mathbf {AM} \cap \mathbf {co{\text{-}}AM} )=\mathbf {AM} \cap \mathbf {co{\text{-}}AM} }
である。
Aiello, William; Håstad, Johan (1991), Statistical Zero-Knowledge Languages Can Be Recognized in Two Rounds , , Journal of Computer and System Sciences 42 : 327–345 Babai, László (1985), “Trading group theory for randomness”, STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing , ACM, pp. 421–429, doi :10.1145/22145.22192 , ISBN 978-0-89791-151-1 Boppana, Ravi B.; Håstad, Johan; Zachos, Stathis (1987), Does co-NP Have Short Interactive Proofs? , , Information Processing Letters (Elsevier North-Holland, Inc.) 25 (2): 127–132, doi :10.1016/0020-0190(87)90232-8 Fortnow, Lance (1987), “The Complexity of Perfect Zero-knowledge”, Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing , ACM, pp. 204–209, doi :10.1145/28395.28418 , ISBN 0-89791-221-7 Goldreich, Oded; Mansour, Yishay; Sipser, Michael (1987), “Interactive proof systems: Provers that never fail and random selection”, IEEE, doi :10.1109/SFCS.1987.35 , ISBN 0-8186-0807-2 Goldwasser, Shafi ; Sipser, Michael (1986), “Private coins versus public coins in interactive proof systems”, STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing , ACM, pp. 59–68, doi :10.1145/12130.12137 , ISBN 978-0-89791-193-1 情報理論とその応用学会 編『暗号と認証』培風館 、1996年。ISBN 4-563-01454-0 。 岡本龍明 ; 太田和夫 編『暗号・ゼロ知識証明・数論』共立出版株式会社、1995年。ISBN 4-320-02740-X 。 Schöning, Uwe (1988), “Graph isomorphism is in the low hierarchy”, J. Comput. Syst. Sci. , 37 , pp. 312–323, doi :10.1016/0022-0000(88)90010-4 Schöning, Uwe (1989), “Probabilistic complexity classes and lowness”, J. Comput. Syst. Sci. , 39 , pp. 84–100, doi :10.1016/0022-0000(89)90020-2 静谷啓樹; 伊東利哉; 桜井幸一ゼロ知識証明モデルと計算量理論『情報処理』第32巻、第6号、673–681頁、1991年。 戸田誠之助 『グラフ同型性判定問題』日本大学文理学部、2001年。ISBN 4-572-99998-8 。 Zachos, Stathis; Furer, Martin (1987), “Probabilistic Quantifiers vs. Distrustful Adversaries”, Proc. Of the Seventh Conference on Foundations of Software Technology and Theoretical Computer Science , Springer-Verlag, pp. 443–455, ISBN 0-387-18625-5
実用的な時間で解けるクラス 実用的な時間で解けないと疑われているクラス 実用的な時間では解けないクラス クラス階層 クラスの族
一覧 ・カテゴリ
![{\displaystyle \mathbf {AM} [{\text{poly}}]^{pc}=\mathbf {AM} [{\text{poly}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/861bc54779f39d4aaa0eb1eff7d385544f6dc2f2)
![{\displaystyle \mathbf {AM} [{\text{poly}}]_{ps}=\mathbf {NP} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/2348969b4324822079eee12e1ba079d9131b8080)
![{\displaystyle \mathbf {IP} [k]\subseteq \mathbf {AM} [k+2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d100300450c0f12600551b97fb23edc19cc16cbf)
