Arthur–Merlinプロトコル

Arthur-Merlinプロトコルについて

概要

Arthur-Merlinプロトコルは、検証者であるArthurと証明者であるMerlinの間で情報がやりとりされる、対話型の証明システムです。このプロトコルでは、公開されている乱数を利用して問題が受理されるか拒否されるかを判断します。検証者Arthurは、確率的に動作する多項式時間のコンピュータであり、証明者Merlinは計算能力が無限に近いオラクルとして機能します。重要なのは、MerlinがArthurに対して必ずしも正確な回答を提供するわけではないため、Arthurはその回答を慎重に吟味する必要がある点です。具体的には、問題の真実の答えが「はい」の場合は、Arthurがその答えを受理する確率が少なくとも2/3に達し、一方で「いいえ」の場合は、受理する確率は最大でも1/3にとどまります。

このプロトコルのユニークな特徴は、Arthurが使用する乱数が公開されていることにあります。したがって、MerlinはArthurの動作方法を正確に予測できるため、このシステムにおいてはインタラクションが発生します。また、Arthur-Merlinプロトコルは、検証者から証明者へ情報が送信されるプロトコルをAM（Arthur-Merlin）と呼び、逆に証明者から検証者への通信が始まるものはMA（Merlin-Arthur）と呼ばれます。

定義

対話型証明を実施する際、証明者Pは無限の計算能力を持つチューリングマシン、検証者Vは確率的多項式時間で動作するチューリングマシンと見なされます。PとVは、それぞれ相互に通信が可能です。両者が通信する過程で、最初に誰が情報を提供するかによってプロトコルが異なります。AMとMAにはそれぞれ性質がありますが、基本的に受理確率において共通の条件が適用されます。

（完全性）ある言語LがAMに属する場合、その言語がLに含まれる場合には、Arthurが受理する確率が2/3以上でなければなりません。逆に、Lに含まれない場合は、すべての証明者に対してArthurが受理する確率は1/3を超えない必要があります。

性質とクラスの関係

AMプロトコル（またはMAプロトコル）は、定数回の動作を持つ言語を示し、これらの多くはAM[2]に分類されます。このことから、AMクラスとMAクラスの間には密接な関係が存在することが確認されています。

AMと他の複雑性クラスとの関係において、特に重要なのは、BPP（Bounded-error Probabilistic Polynomial time）とMA、さらにAMの関係です。AMは、複雑性理論におけるさまざまなクラスの重要な橋渡し役を果たしており、特にBPPとの関連が考えられています。

具体的な問題

具体的な例としては、グラフ非同型問題（GNI）が挙げられます。この問題では、2つの与えられたグラフが同型でないことを判定する必要があります。このような問題は、AMにきれいにフィットする特性を持っています。

結論

Arthur-Merlinプロトコルは、確率的な通信を特徴とし、証明者の情報を活用して問題を解決するためのシンプルかつ強力な枠組みです。AMとMAは、対話型証明システムにおける異なるアプローチを示し、情報理論と計算複雑性の分野における理解を深める上で重要な役割を果たしています。

もう一度検索