対話型証明系 対話型証明系の概要

ウィキペディア

対話型証明系

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/12/15 06:53 UTC 版)

対話型証明系は、必ず次のような2つの要求に従う。

• 完全性: 文が真である場合、プロトコルに正しく従う検証者は、プロトコルに正しく従う証明者の証明に納得する。
• 健全性: 文が偽である場合、証明者がプロトコルに正しく従うかどうかに関わらず、プロトコルに正しく従う検証者は証明者の（真であるという）証明には従わない（小さな確率で納得してしまう可能性はある）。

なお、検証者がプロトコルに従わない場合は問題とはされず、常に検証者を信じるという点に注意されたい。

この系の特徴や関連する複雑性クラスが認識する言語の特徴は、検証者がどのように制限されるかに依存し、また検証者にどのような能力を与えるかに依存する。例えば、多くの対話型証明系は検証者の無作為選択能力に大きく依存する。交換されるメッセージの性質、その頻度や内容も重要である。対話型証明系は、それまで単一の機械で定義されてきた複雑性クラスに多大な影響を与えた。対話型証明系を使って定義された主な複雑性クラス（実際には複雑性クラスの階層）としては、AM、MA、IP、PCP などがある。

NP

よく知られている複雑性クラス NP は非常に単純な対話型証明系で定式化できる。この場合、検証者は決定的な多項式時間の機械である（つまり、Pマシン）。プロトコルは次の通り。

• 証明者は入力を見て、その無限の計算能力を使って解を計算し、証明の証拠となる多項式長のメッセージを返す。
• 検証者はその証拠を決定的な多項式時間で検証する。妥当であれば、それを受理し、そうでなければ拒絶する。

妥当な証明の証拠がある場合、証明者は常に検証者が受理するような証拠を与えることができる。妥当な証明の証拠がない場合、入力が言語に属していないということであり、いかなる証拠も受理されないので、悪意のある証明者であったとしても検証者を納得させられない。

Arthur-Merlin プロトコルと Merlin-Arthur プロトコル

NP をより対話的に定式化することもできるが、そのような対話による計算の概念は1985年になって登場した。それは、László Babai の発表した "Trading group theory for randomness" という論文で定義された Arthur-Merlin（AM）クラス階層によるものである。その中で Arthur（検証者）は確率的多項式時間機械であり、Merlin（証明者）は無限の計算資源を持つ機械である。

クラス MA は、上述の NP の対話の単純な一般化であり、検証者は確率的ではなく決定的である。また、検証者が常に妥当な証拠を受理して妥当でないものを拒絶するのではなく、以下のようにもっと寛大な方針を採用する。

• 完全性: 文字列が言語に属する場合、証明者は検証者が受理するような証拠を最低でも 2/3 の確率で与えることができる（検証者の無作為選択に依存する）。
• 健全性: 文字列が言語に属さない場合、悪意の有無に関わらず、証明者が検証者が受理するような証拠を与えることができる確率は 1/3 未満である。

これは、通常のNPの対話プロトコルよりも強力であり、BPPのアルゴリズムが実用的であるように、このような確率的な証拠であっても検証に値する。Babai の提唱した他のクラスについては後述する。

公開硬貨と秘密硬貨

Babai がMAの証明系を定義した直後、シャフィ・ゴールドワッサーらは IP[f(n)] の対話型証明系を定義した論文のドラフト版を発表した。これは MA プロトコルと同様のマシン構成だが、入力長 n に対して f(n) 回のラウンドが許されていた。各ラウンドで、検証者は計算を行って証明者にメッセージを渡し、証明者も計算を行って検証者にメッセージを返す。そして全ラウンドの最後に検証者は決定しなければならない。例えば、IP[3] プロトコルなら、メッセージの並びは VPVPVPV となる。ここで、V は検証者のターン、P は証明者のターンである。

Arthur-Merlin プロトコルでは、Babai は同様のクラスを AM[f(n)] と定義した。これも f(n) 回のラウンドを許すものだが、彼はマシンに条件を1つ追加した。検証者は証明者に対して計算に使用したランダムビット列を全て提示しなければならないというものである。結果として検証者は証明者に対して何も隠せないことになる。なぜなら証明者の計算能力は無限なので、ランダムビット列さえ分かれば、検証者の計算を全てシミュレート可能だからである。ランダムビット列（硬貨投げ）が両方のマシンから見えるため、これを「公開硬貨」プロトコルと呼ぶ。一方 IP の手法を対照的に「秘密硬貨」プロトコルと呼ぶ。

公開硬貨の基本的な問題は次のようなものである。証明者が言語に属さない文字列を検証者に悪意を持って受理させようとした場合、検証者が内部状態を見せないようにするためにして証明者の計画を妨害する可能性がある。この問題があるため、IP 証明系が定義された。

1986年、ゴールドワッサーとシプサーは驚くべき結果を示した。すなわち、IP で認識できる言語は、Arthur-Merlin 公開硬貨プロトコルでも2ラウンド追加するだけで認識可能であり、結果としてほとんど差がないことがわかったのである。つまり、公開硬貨プロトコルも秘密硬貨プロトコルもほぼ同じであることが示された。実際、Babai は 1988年、任意の定数 k について AM[k] が IP[k] と比較して劣らないことを示した。