対話型証明システム

複雑性クラスNPは、非常に単純な証明システムと見なすことができる。このシステムでは、検証者は決定性多項式時間マシン（Pマシン）である。プロトコルは以下のとおりである。

• 証明者は入力データを見て、自身の無制限の計算能力を用いて解を計算し、多項式サイズの証明証明書を返す。
• 検証者は、証明書が有効かどうかを決定論的な多項式時間で検証します。有効な場合は承認し、そうでない場合は拒否します。

有効な証明証明書が存在する場合、証明者はその証明書を検証者に提示することで、常に検証者を納得させることができます。しかし、有効な証明証明書が存在しない場合、入力は該当言語ではないため、どんなに悪意のある証明者であっても、検証者を説得することはできません。なぜなら、いかなる証明証明書も拒否されるからです。

NPは相互作用を利用していると見なされるかもしれないが、相互作用による計算の概念が（複雑性理論の文脈で）2つの独立した研究者グループによって考案されたのは1985年になってからのことだった。1つのアプローチは、 ラースロー・ババイが「ランダム性のための群論の交換」^{[ 2 ]}を発表し、アーサー・マーリン（AM ）クラスの階層を定義した。このプレゼンテーションでは、アーサー（検証者）は確率的多項式時間マシンであり、マーリン（証明者）は無制限のリソースを持っている。

特にMAクラスは、上記のNP相互作用を単純に一般化したもので、検証者が決定論的ではなく確率論的であるという点が異なります。また、検証者が常に有効な証明書を受け入れ、無効な証明書を拒否することを要求するのではなく、より寛容な性質を持っています。

• 完全性：文字列が対象言語に含まれる場合、証明者は、検証者が少なくとも2/3の確率で（検証者のランダムな選択に応じて）受け入れるような証明書を発行できなければならない。
• 健全性:文字列が言語に含まれていない場合、どんなに悪意のある証明者であっても、検証者にその文字列を受け入れるよう説得できる確率は 1/3 を超えません。

このマシンは通常のNPインタラクションプロトコルよりも強力である可能性があるが、 BPPアルゴリズムは実用的な計算を抽象化すると考えられているため（BPPを参照）、証明書の検証は実用的である。

公開型コインプロトコルでは、検証者が行ったランダムな選択は公開されます。一方、非公開型コインプロトコルでは、それらは非公開のままです。

Babai がMAの証明システムを定義したのと同じ会議で、Shafi Goldwasser、Silvio Micali、Charles Rackoff ^{[ 3 ]}は対話型証明システムIP [ f ( n )]を定義する論文を発表しました。これはMAプロトコルと同じマシンを使用しますが、入力サイズnに対してf ( n )ラウンドが許可されます。各ラウンドで、検証者は計算を実行して証明者にメッセージを渡します。証明者は計算を実行して情報を検証者に返します。最後に、検証者は決定を下す必要があります。たとえば、IP [3] プロトコルでは、シーケンスは VPVPVPV となり、V は検証者のターン、P は証明者のターンです。

アーサー・マーリン・プロトコルにおいて、ババイは同様のクラスAM [ f ( n )] を定義し、f ( n ) ラウンドを許可したが、マシンに1つの追加条件を課した。それは、検証者が計算で使用するすべてのランダムビットを証明者に示さなければならないという条件である。その結果、検証者は証明者から何も「隠す」ことができない。なぜなら、証明者は検証者が使用したランダムビットを知っていれば、検証者が行うすべてのことをシミュレートできるほど強力だからである。これは、ランダムビット（「コイン投げ」）が両方のマシンから見えるため、公開コイン・プロトコルと呼ばれる。これに対し、 IPアプローチはプライベート・コイン・プロトコルと呼ばれる。

公開コインの根本的な問題は、証明者が悪意を持って検証者に言語に含まれていない文字列を受け入れさせようとした場合、検証者が内部状態を証明者から隠蔽できれば、その企みを阻止できる可能性があるという点にある。これがIP証明システムを定義する際の主要な動機の一つであった。

1986年、GoldwasserとSipser ^{[ 4 ]} は、おそらく意外なことに、検証者が証明者からコイン投げを隠す能力は結局あまり役に立たないことを示した。なぜなら、わずか2ラウンド多いだけのArthur–Merlin公開コインプロトコルで、同じ言語をすべて認識できるからである。結果として、公開コインプロトコルとプライベートコインプロトコルはほぼ同等である。実際、Babaiが1988年に示したように、すべての定数kに対してAM [ k ]= AMであるため、IP [ k ]はAMに対して何の利点もない。^{[ 5 ]}

これらのクラスの強力さを示すために、グラフ同型問題、つまりあるグラフの頂点を置換して別のグラフと同一にできるかどうかを判定する問題を考えてみましょう。この問題は、証明証明書がグラフを等しくする置換であるため、 NPに属します。グラフ同型問題の補問題であるco- NP問題はNPに属することが知られていませんが、AMアルゴリズムが存在し、それを確認する最良の方法はプライベート コイン アルゴリズムを使用することです。^{[ 6 ]}

プライベートコインは役に立たないかもしれないが、より多くの相互作用ラウンドは役に立つ。確率的検証マシンと全能の証明機が多項式数のラウンドで相互作用することを許容すると、IPと呼ばれる問題のクラスが得られる。1992 年、アディ・シャミアは複雑性理論の中心的な結果の 1 つは、 IP が多項式空間で通常の決定性チューリングマシンによって解決可能な問題のクラスであるPSPACEに等しいことを明らかにした。^{[ 7 ]}

システムの要素が量子計算を使用することを許可すると、システムは量子対話型証明システムと呼ばれ、対応する複雑性クラスはQIPと呼ばれます。^{[ 8 ]}一連の結果が、2010 年にQIP = PSPACEという画期的な発見につながりました。^{[ 9 ] [ 10 ]}

対話型証明システムは、 NPに含まれないと考えられている問題を解決できるだけでなく、一方向関数の存在に関する仮定の下では、証明者は検証者に解決策に関する情報を一切与えずに、検証者に解決策を納得させることができます。これは、検証者が完全な解決策を信頼できない場合に重要です。検証者が証明書を見たことがないのに、解決策が存在することを検証者に納得させることは最初は不可能に思えますが、ゼロ知識証明として知られるそのような証明は、実際にはNPのすべての問題に存在すると考えられており、暗号学で価値があります。ゼロ知識証明は、特定の数論的言語について Goldwasser、Micali、Rackoff による 1985 年のIPに関する最初の論文で初めて言及されました。しかし、その力の程度は、Oded Goldreich、Silvio Micali、Avi WigdersonによってNP全体について示され、^{[ 6 ]}これはRussell ImpagliazzoとMoti YungによってIP全体に初めて拡張されました。^{[ 11 ]}

IP の設計者の目標の 1 つは、可能な限り強力な対話型証明システムを作成することでしたが、当初は検証者をより強力にして実用的でなくすることなく、それをより強力にすることはできないように思われました。Goldwasser らは、1988 年の「マルチ証明者対話型証明: 扱いにくさの仮定を取り除く方法」でこれを克服し、2 つの独立した証明者が存在するMIPと呼ばれるIPの変種を定義しました。^{[ 12 ]}検証者が 2 つの証明者にメッセージを送信し始めると、2 つの証明者は通信できなくなります。犯罪者とそのパートナーを別々の部屋で尋問すれば、犯罪者が嘘をついているかどうかを判断しやすくなるのと同様に、検証者が言語にない文字列を受け入れるように騙そうとする悪意のある証明者を検出するには、検証者が二重チェックできる別の証明者がいる方がはるかに簡単です。

実際、これは非常に役立つため、Babai、Fortnow、およびLundは、MIP = NEXPTIME 、つまり指数時間で非決定性マシンによって解けるすべての問題のクラスであることを示すことができました。これは非常に大きなクラスです。^{[ 13 ]} NEXPTIMEはPSPACEを含み、厳密にPSPACEを含むと考えられています。2つを超える定数数の追加証明器を追加しても、それ以上の言語を認識できるようになります。この結果は、この定理の「縮小版」と考えることができる有名なPCP定理への道を開きました。

MIPには、 IPが行う必要のある一方向関数の仮定なしに、NPのすべての言語に対するゼロ知識証明を記述できるという便利な特性もあります。これは、証明可能な破られない暗号アルゴリズムの設計に関係しています。^{[ 12 ]}さらに、MIPプロトコルは、定数ラウンドでIPのすべての言語を認識でき、3番目の証明者を追加すると、定数ラウンドでNEXPTIMEのすべての言語を認識できるため、 IPに対するその優位性を再び示しています。

任意の定数kに対して、 k 個の証明者と多項式個のラウンドを持つ MIP システムは、2 つの証明者と定数個のラウンドを持つ同等のシステムに変換できることが知られています。 ^{[ 14 ]}

IPの設計者たちはババイの対話型証明システムの一般化を検討したが、他の設計者たちは制限を検討した。非常に有用な対話型証明システムはPCP（f（n）、g（n ））であり、これはMAの制限で、アーサーはf（n ）個のランダムビットしか使用できず、マーリンから送られた証明証明書のg（n ）個のビットしか調べることができない（実質的にランダムアクセスを使用する）。

様々なPCPクラスに関する、証明しやすい結果が数多く存在する。${\displaystyle {\mathsf {PCP}}(0,{\mathsf {poly}})}$ランダム性を持たないが証明書にアクセスできる多項式時間機械のクラスは、まさにNPである。${\displaystyle {\mathsf {PCP}}({\mathsf {poly}},0)}$多項式時間で多項式個のランダムビットにアクセスできるマシンのクラスはco- RPである。AroraとSafraの最初の主要な結果は、${\displaystyle {\mathsf {PCP}}(\log ,\log )={\mathsf {NP}}}$言い換えれば、NPプロトコルの検証者が選択できるのは${\displaystyle O(\log n)}$証明書の一部を確認する必要があるが、それが${\displaystyle O(\log n)}$ランダムなビットを使用する。 ^{[ 15 ]}

さらに、PCP定理は、証明アクセス回数を定数まで減らすことができると主張している。つまり、${\displaystyle {\mathsf {NP}}={\mathsf {PCP}}(\log ,O(1))}$[ ^{16 ]}彼らはNPのこの貴重な特徴付けを利用して、 P = NPでない限り^、特定のNP完全問題化バージョンには近似アルゴリズムが存在しないことを証明した。このような問題は現在、近似の困難性として知られる分野で研究されている。