対話型証明システム
証明システムのうち、証明者と検証者が対話的に動作する証明システムを対話型証明システム（interactive proof system）と呼びます。逆に、証明者が検証者へメッセージを送信したら、検証者が検証に取り掛かる証明システムを非対話型証明システムと呼びます。ここでは、対話型証明システムを定義します。
対話型Turingマシン
対話型証明システムを定義するために、その構成要素となる対話型Turingマシン（interactive Turing machine; ITM）について説明します。ITMとは、以下の複数のテープを持つTuringマシンです。
- 読み出し専用の入力テープ
- 読み出し専用のランダムテープ
- 読み書き可能な作業テープ
- 書き込み専用の出力テープ
- 読み出し専用の通信テープ
- 書き込み専用の通信テープ
- 読み書き可能なスイッチテープ
さらに、ITMはアイデンティティと呼ばれる1ビットの情報 \(\sigma \in \lbrace 0,1 \rbrace\) を持ちます。スイッチテープの内容がアイデンティティ \(\sigma\) と一致する場合、そのITMはアクティブ状態にあり、一致しない場合、そのITMはアイドル状態にあります。
以下、入力テープの内容を入力、ランダムテープの内容をランダム入力、終了時の出力テープの内容を出力と呼びます。
スイッチテープとアイデンティティについて説明します。まず、前提として対話型証明システムでは、2つの対話型Turingマシンが対話的に通信を行うことを考えます。対話的な通信を形式的に表現するために、片方のマシンがアクティブ状態にあり、もう片方のマシンがアイドル状態にある状況を作り出す必要があります。そのためにアイデンティティとスイッチテープがあります。片方のアイデンティティを \(0\) 、もう片方のアイデンティティを \(1\) とします。スイッチテープは2つのマシンが共有しています。スイッチテープの内容とアイデンティティが一致するマシンが処理を行い、メッセージを送り終わったらスイッチテープの内容を自分のアイデンティティからもう片方のアイデンティティに切り替えることで、もう片方のマシンが処理を開始します。これが交互に行われることで通信を表現します。片方のマシンが停止し、かつ、スイッチテープの内容がそのマシンのアイデンティティである場合、両方のマシンの出力が決定します。
通信テープについて説明します。読み出し専用の通信テープはもう片方のマシンの書き込み専用の通信テープは同じテープです。自身の書き込み専用の通信テープに書き込むことで、相手のマシンにメッセージを送ることができます。
通信テープとスイッチテープは両方のマシンで共有します。入力テープは、両方のマシンで共有する場合と共有せず個々のテープを持つ場合を考えることがありますが、このサブセクションでは入力テープを共有する場合を考えます。それ以外のテープは共有しません。
ランダムテープは、無限のバイナリ列からランダムに選択されます。そのため、対話型Turingマシンは定義としては確率的Turingマシンではないものの、事実上確率的に動作します。
対話型証明システムの定義
対話型証明システムを定義します。
対話型証明システム
証明者と検証者のマシンをそれぞれ \(P,V\) とし、マシン \(V\) が多項式時間で動作して、以下で定義する完全性と健全性が成り立つなら、対話型マシンの組 \((P,V)\) を言語 \(\mathcal{L}\) の対話型証明システムという。
各マシンのランダム入力（ランダムテープの内容）が一様かつ独立に選択されたとき、共通の入力 \(x\) でマシン \(A\) と通信するときの \(B\) の出力を表す確率変数を \(\langle A,B \rangle (x)\) と表記する。完全性と健全性は、次のように定義される。
完全性: 任意の文字列 \(w \in \mathcal{L}\) に対して、次の式が成り立つ。
健全性: 任意の文字列 \(w \in \mathcal{L}\) と任意の対話型マシン \(P^*\) に対して、次の式が成り立つ。
共通の入力には証明したいステートメントが含まれます。
確率 \(\frac{1}{3}\) は誤り確率と呼ばれ、 \(0\) 以上 \(\frac{1}{2}\) 未満の数であれば任意です。 \(e_1,e_2\) を \(0\) 以上 \(\frac{1}{2}\) 未満の適当な定数として、完全性と健全性の不等号の右辺をそれぞれ \(1 - e_1,\ e_2\) にしても問題ありません。この誤り確率は \(\mathrm{BPP}\) と同様に増幅補題により指数関数的に小さくできます。すなわち、完全性は \(\ge 1\) に、健全性は \(\le 0\) に近づけるということです。よって、完全性と健全性はともに統計的であり、統計的完全性と統計的健全性です。
完全性においては、ある証明者のマシン \(P\) を対象とするのに対し、健全性においては任意の証明者のマシン \(P^*\) を対象としています。また、検証者のマシン \(V\) は多項式時間で動作するのに対して、証明者のマシン \(P,P^*\) には計算能力の制限はないことに注意してください。
証明者あるいは検証者が1つのメッセージを送信することの単位を「ムーブ」（move）、1つの対話の単位を「ラウンド」（round）と呼びます。つまり、1ラウンドは、2ムーブになります。
対話型証明の例: グラフ非同型性判定問題
対話型証明の例として「グラフ非同型性判定問題」（graph non-isomorphism problem）を題材とします。まず、グラフ \(G\) と \(G'\) があり、グラフ \(G\) の頂点を並び替えてグラフ \(G'\) に一致できるとき、グラフ \(G\) と \(G'\) は同型（isomorphic）であると言います。形式的には次のようになります。
グラフの同型
グラフ \(G,G'\) の頂点集合をそれぞれ \(V,V'\) 、辺集合をそれぞれ \(E,E'\) とする。ある全単射写像 \(f\) が存在して、グラフ \(G\) の任意の2頂点 \(u,v \in V\) に対して、 \((u,v) \in E\) ならば \((f(u),f(v))\in E'\) であるとき、グラフ \(G\) と \(G'\) を同型であるという。
2つのグラフが与えられてそれらが同型であるかを判定する問題をグラフ同型性判定問題といいます。このグラフ同型性判定問題は、明らかにクラス \(\mathrm{NP}\) に属しますが、まだ多項式時間アルゴリズムが見つかっておらず、クラス \(\mathrm{P}\) に属するかがわかっていません。また、 \(\mathrm{NP}\) 完全であることも証明されていません。
グラフ同型性判定問題の補言語であるグラフ非同型性判定問題を考えます。グラフが非同型であることを示す簡単な証明を与える方法はまだ見つかっていないため、グラフ非同型性判定問題はクラス \(\mathrm{NP}\) に属するかがわかっていません。しかし、証明者が2つのグラフ \(G,G'\) が非同型であることを検証者に納得させる対話型証明システムを以下のように構成できます。
まず、検証者はグラフ \(G,G'\) からランダムに一つ選びます。その選んだグラフの頂点をランダムに並び替え、その並び替えたグラフを \(H\) とします。検証者はグラフ \(H\) を証明者に送り、グラフ \(H\) がグラフ \(G,G'\) のどちらかを尋ねます。もしグラフ \(G,G'\) が非同型であるならば、証明者は必ず正しくこの質問に答えられますが、グラフ \(G,G'\) が同型である場合、証明者にどれだけ計算能力があろうとも証明者は \(\frac{1}{2}\) の確率で間違えてしまいます。よって、複数回この質問を繰り返すことで、検証者は2つのグラフが非同型であると納得できます。ただし、このプロトコルではグラフ同型であることを示すことはできません。
対話型証明システムの計算複雑性クラス
計算複雑性クラス \(\mathrm{IP}\) を、対話型証明システムを持つ全ての言語の集合として定義します。
\(\mathrm{NP}\) の全ての言語は、(1) 証明者が検証者にステートメントとウィットネスを送り、(2) 検証者がそれを検証する、という流れの対話型証明システムを構成できます。なので、 \(\mathrm{NP}\) を、
- 証明者と検証者の両方が決定性を持ち、
- 相互作用が証明者から検証者へ一方向的で、
- 検証者が決して誤らない、
という3つの性質を持つ対話型証明システムのクラスとして捉えることができます。よって、 \(\mathrm{NP} \subseteq \mathrm{IP}\) が成り立ちます。また、 \(\mathrm{IP} = \mathrm{PSPACE}\) であることが知られています。
検証者の内部のコイントス（すなわち乱数）を公開しなければならないとする対話型証明システムを考えることができます。そのような対話型証明システムはパブリックコインであるといい、Arthur–Merlinプロトコルと呼ばれます。逆にコイントスを公開しない対話型証明システムはプライベートコインであるといいます。
コイントスを公開するか否かを考える意義は、検証者が悪意ある証明者に対して、内部で使用する乱数を秘密にすれば、証明者が証明を偽造することを阻止できるかもしれない、というモチベーションからです。例えば、先程紹介したグラフ非同型性判定問題の対話型証明システムにおいて、検証者がグラフ \(G,G'\) のどちらかを選びますが、これを秘密にしないと悪意ある証明者が100%の確率でグラフを当てることができてしまいます。このようなことから、直感的にはコイントスを秘密することで対話型証明システムを構築できる言語が多くなってもおかしくないと思えます。
しかし、検証者が内部のコイントスを秘匿しても、対話型証明システムを構築できる言語の集合は全く変わらないことが証明されています。この事実について少し説明します。
計算複雑性クラス \(\mathrm{AM}\) を、検証者が最初に行動し、パブリックコインである、2ラウンドの対話型証明システムを持つ全ての言語の集合であるとします。また、\(\mathrm{AM}\) のラウンドを \(k\) に拡張した計算複雑性クラスを \(\operatorname{AM}[k]\) とします。 \(k\) は定数とは限らず、多項式にもなり得ます。定義より、次の式が成り立ちます。
\(\mathrm{IP}\) に対してもラウンドを \(k\) に限定した \(\operatorname{IP}[k]\) を定義します。まず、 \(\operatorname{AM}[k]\) は \(\operatorname{IP}[k]\) をパブリックコインに限定しただけなので、任意の \(k\) に対して次の関係が成り立ちます。
そして、任意の定数 \(k\) に対して、次の関係が成り立つことが証明されています。
これは、対話型証明システムをプライベートコインにしたところで、それに対応する2ラウンド増やしたパブリックコインの対話型証明システムが存在することを意味しています。また、任意の定数 \(k>2\) に対して次の式が成り立つことが証明されています。
パブリックコインの対話型証明システムを構築できる全ての言語は2ラウンドで構築できるということです。以上より、次の式が成り立ちます。
結局、 \(\operatorname{IP}[k]\) は \(\mathrm{AM}\) に存在しない言語に対して対話型証明システムを構築できるわけではないので、プライベートコインにしたところで対応できる言語の種類の観点から見れば全く意味がないということです。もちろん実際の対話型証明システムでは、言語の種類だけでなく効率性など他の軸も存在するので、対応できる言語が変わらないからと言ってプライベートコインの必要性が無くなるわけではありません。
慣習上の注意として、 \(\mathrm{AM}\) は定義より定数ラウンドという条件が入る一方で、 \(\mathrm{IP}\) は定数ラウンドだけでなく多項式ラウンドも考慮するため、 \(\mathrm{AM}\neq \mathrm{IP}\) であり \(\mathrm{AM} \subseteq \mathrm{IP}\) となることに注意してください。つまり、 \(\mathrm{AM} = \operatorname{AM}[2]\) ですが、 \(\mathrm{IP}=\operatorname{IP}[\mathrm{poly}]\) であるということです。なので、\(\operatorname{AM}[\mathrm{poly}] = \operatorname{IP}[\mathrm{poly}]\) とは言えます。