Arthur-Merlin games アーサー・マーリン・プロトコル

アーサー・マーリン・プロトコル（Arthur-Merlin games）は、計算複雑性理論において「対話」と「乱数」の計算パワーを定義したモデルです。1985年にラズロ・ババイ（László Babai）によって提唱されたこのモデルは、一見すると「ただのクイズ」のように見えますが、現代の暗号理論や証明論の礎となっています。

1. 登場人物と役割

このモデルには、能力の対照的な二人が登場します。

• アーサー (Arthur): 王であり、検証者。
  • 計算能力は普通（多項式時間で動くコンピュータと同等）。
  • コイン（乱数）を投げることができ、その結果をマーリンに正直に伝えます。
• マーリン (Merlin): 魔法使いであり、証明者。
  • 計算能力は無限（全知全能）。
  • アーサーに自分の主張が正しいことを認めさせようとします。嘘をつく可能性もあります。

2. 公開コイン (Public Coin) という特徴

アーサー・マーリン・プロトコル（AM）の最大の特徴は、アーサーが投げるコインの結果が「マーリンにも完全に見えている」という点です。

• 秘匿コイン (Private Coin): 検証者が自分だけの手元で乱数を生成する（一般的な対話型証明：IP）。
• 公開コイン (Public Coin): 検証者が投げた乱数が、全世界（証明者）に公開されている（AM）。

一見、マーリンに手の内を明かす「公開コイン」の方がアーサーにとって不利（検証が弱い）に思えます。しかし、ゴールドワッサーとシプサーの定理によって、「秘匿コインで証明できることは、公開コインでも証明できる」ことが示されました。これは当時の計算機科学界にとって大きな驚きでした。

3. クラス AM とその階層

計算量のクラスとしての AM は、「アーサーがメッセージを送（コインを投げ）し、マーリンがそれに応答する」という1往復のやり取りで検証できる問題の集合を指します。

• NP ⊆ AM: もしマーリンがただ答え（証拠）を送るだけなら、それは NP 問題と同じです。
• AM ⊆ PSPACE: 対話で解決できることは、メモリを多項式量使えば自力で計算可能です。

特に、「グラフ非同型性問題（2つのグラフが異なる構造であることの証明）」が AM に属することが示されたことは、このクラスの強力さを証明する重要なエピソードとなりました。

4. 「アーサー・マーリン」の機能性

経営や投資のデランダマイズという文脈において、AMプロトコルは以下の示唆を与えます。

• 透明性の力: 検証者（アーサー）が自分の「問い（乱数）」を完全に公開していても、証明者（マーリン）が嘘をつけない構造を作れる。
• 確率的な確信: たった数回のやり取りで、アーサーはマーリンの主張が正しいことを、統計的にほぼ間違いのないレベルで確信できる。

階層図

$$P \subseteq NP \subseteq AM \subseteq IP = PSPACE$$

そしてこの理論の帰結はどんな難問も構成的に証明することなしに、コストゼロでその真正性が検証可能であるという事実である。

どんな難問も検証できる」という事実は、IP = PSPACE という等式によって記述される。この定理が人類に与えた究極の武器は、「解く能力（Solvability）」と「真偽を判定する能力（Verifiability）」を完全に分離したことにあります。

1. 「理解」を超えた「検証」

これまでの人類は、「理解できないものは解決できない」と信じてきました。しかし、IP（対話型証明）はこう言います。

「証明者がどれほど高次元（PSPACE）な存在であっても、検証者が正しいクエリ（多項式時間）を投げれば、その真偽を『理解』せずとも『確信』できる」

人事、経営、投資。これらが「難問」だったのは、検証者が証明者と同じレベルの計算を自力で行おうとしていたからです。対話型システムを使えば、全知全能（市場や宇宙）に計算を肩代わりさせ、自分は数回の抜き打ち検査（クエリ）だけでその果実を確定させる側に回れます。

2. Pクラスへの引き摺り下ろし

「Management is P-class」 という命題は、この対話型証明システムを「実装」した瞬間に完成します。

• 証明: 経営上のあらゆる「難問」は PSPACE の範疇に収まります。
• 解決: IP = PSPACE なので、多項式時間（P）の検証者が、適切なインタラクションを通じてその最適解を確定させることができます。
• 結果: 経営は、試行錯誤の闇から、「事業ドメインは情報の非対称性を維持するNPクラスだが、対話によって真実を抽出するだけの Pクラスの作業」へと成り下がります。

3. ABテストという「審判」

あらゆる難問が「ABテストになりさがる」という洞察は、この理論の終着点です。

多項式の算術化によって、宇宙の複雑さは「特定の点での値が一致するかどうか」という、究極の二択（geodesic的なgeometry）に集約されます。

• かつての難問: 「この投資は成功するか？」
• 対話型証明後の解決: 「この多項式の x=k における値は、マーリンの主張と一致するか？（Yes/No）」

結論：検証者（アーサー）は宇宙を有効活用する

このシステムを使えば、proverはもはや「難問を解く人」である必要はありません。proverは宇宙に正しく問い、嘘を許さない検証者（アーサー）としての顔をもつことにより、最小限のコスト（クエリ）で最大限の真実（価値）を確定させる存在になります。

「解決できない問題があるのではない。対話のプロトコルが不適切なだけである。」