確率的に検証可能な証明

計算複雑性理論において、確率的に検証可能な証明( PCP ) とは、有限量のランダム性を使用し、証明の有限数のビットを読み取るランダム化アルゴリズムによって検証できる証明の一種である。この場合、アルゴリズムは、非常に高い確率で正しい証明を受け入れ、誤った証明を拒否する必要がある。検証者ベースの複雑性クラスNPの定義で使用される標準証明 (または証明書)も、チェック手順が証明全体を決定論的に読み取り、常に正しい証明を受け入れ、誤った証明を拒否するため、これらの要件を満たしている。しかし、それらを興味深いものにしているのは、本質的にランダム性を使用して証明のほんの数ビットを読み取るだけで確認できる、確率的に検証可能な証明が存在することである。

確率的に検証可能な証明は、必要なクエリの数と使用されるランダム性の量に応じて、多くの複雑性クラスを生み出します。クラスPCP [ r ( n ), q ( n )] は、最大r ( n ) のランダムビットを使用し、最大q ( n ) ビットの証明を読み取ることで多項式時間で検証できる、確率的に検証可能な証明を持つ決定問題の集合を指します。^[1]特に指定がない限り、正しい証明は常に受け入れられ、不正確な証明は 1/2 を超える確率で拒否されます。計算複雑性理論の主要な結果であるPCP 定理は、 PCP [ O (log n ), O (1)] = NPと述べています。

決定問題 L (またはアルファベット集合 Σ を持つ言語L )が与えられた場合、完全性c ( n ) および健全性s ( n ) (0 ≤ s ( n ) ≤ c ( n ) ≤ 1 ) を持つLの確率的に検証可能な証明システムは、証明者と検証者から構成されます。長さ n の、偽である可能性のある解 x が与えられた場合、証明者は、x がL を解く( x ∈ L、証明は文字列∈ Σ ^∗ )という証明π を生成します。検証者は、ランダム化されたオラクルチューリングマシンV (検証者) であり、 x がL を解く(またはx ∈ L )というステートメントについて証明π をチェックし、ステートメントを受け入れるかどうかを決定します。このシステムには、次のプロパティがあります。

• 完全性: 任意のx ∈ Lに対して、システムの証明者によって生成された証明πが与えられた場合、検証者は少なくともc ( n ) の確率でステートメントを受け入れる。
• 健全性: 任意のx ∉ Lに対して、任意の証明πに対して、検証者は最大でs ( n ) の確率でステートメントを誤って受け入れます。

検証者の計算の複雑さについては、長さnのすべてのxにわたってV が使用するランダムビットの最大数を測定するためのランダム性複雑さ r ( n ) があり、検証者のクエリ複雑さq ( n ) は、長さnのすべてのxにわたってV がπ に対して行うクエリの最大数です。

上記の定義では、証明の長さについては言及されていません。これは、通常、証明にはアルファベット セットとすべての証拠が含まれるためです。証明者にとって、問題の解決方法に到達する方法は重要ではありません。重要なのは、解決方法が言語に属していることの証明だけです。

検証者は、以前のクエリに対する回答を受け取る前にすべてのクエリを実行する場合、 非適応型であると言われます。

複雑性クラスPCP _{c ( n ), s ( n )} [ r ( n ), q ( n )]は、完全性c ( n ) と健全性s ( n )のバイナリアルファベット上の確率的に検証可能な証明システムを持つすべての決定問題のクラスです。検証者は非適応型で、多項式時間で実行され、ランダム性複雑性r ( n ) とクエリ複雑性q ( n )を持ちます。

PCP _{1, 1/2} [ r ( n ), q ( n ) ]の代わりに、省略表記PCP [ r ( n ), q ( n ) ]が使用されることがあります。複雑性クラスPCP は、 PCP _{1, 1/2} [ O (log n ), O (1)]と定義されます。

確率的に検証可能な証明の理論は、さまざまなパラメータの制約（完全性、健全性、ランダム性の複雑さ、クエリの複雑さ、アルファベットのサイズ）の下での確率的に検証可能な証明システムの能力を研究します。これは、計算の複雑さ（特に近似の困難さ）と暗号化に応用されています。

確率的に検証可能な証明の定義は、1992年にアローラとサフラによって明示的に導入されましたが^[2]、その性質は以前に研究されていました。1990年にババイ、フォートナウ、ルンドはPCP [poly( n ), poly( n )] = NEXPであることを証明し、標準証明（ NEXP ）と確率的に検証可能な証明の間の非自明な同値性を初めて示しました。^[3] 1992年に証明された PCP定理は、 PCP [ O (log n ), O (1)] = NPであると述べています。^{[2] [4]}

近似の困難性の理論では、確率的に検証可能な証明における完全性、健全性、アルファベットのサイズ、およびクエリの複雑さの役割を詳細に理解する必要があります。

計算の複雑さの観点から見ると、パラメータの極端な設定では、確率的に検証可能な証明の定義は標準的な複雑さのクラスと同等であることが容易にわかります。たとえば、PCP [ r ( n ), q ( n )] の異なる設定では次のようになります。

• PCP [0, 0] = P ( P はランダム性がなく、証明にアクセスできないものと定義されます。)
• PCP [ O (log( n )), 0] = P (対数個のランダムビットは、多項式時間チューリングマシンには役立ちません。対数長さのすべてのランダム文字列を多項式時間で試すことができるからです。)
• PCP [0, O (log( n ))] = P (ランダム性がない場合、証明は固定された対数サイズの文字列と考えることができます。多項式タイムマシンは、多項式時間ですべての可能な対数サイズの証明を試すことができます。)
• PCP [poly( n ), 0] = coRP ( coRPの定義により)
• PCP [0, poly( n )] = NP（検証者ベースのNPの定義による。）

PCP 定理とMIP = NEXP は次のように特徴付けられます。

• PCP [ O (log n ), O (1)] = NP (PCP定理)
• PCP [ポリ( n ), O (1)] = PCP [ポリ( n ),ポリ( n )] = NEXP ( MIP = NEXP )。

PCP [ r ( n ), q ( n )] ⊆ NTIME (poly( n ,2 ^{O ( r ( n ))} q ( n )))であることも知られています。特に、PCP [log n , poly( n )] = NPです。一方、NP ⊆ PCP [ o (log n ), o (log n )]の場合、P = NPです。^[2]

線形 PCP は、証明が有限体 の要素のベクトルであり、PCP オラクルはその証明に対して線形演算のみを実行できる PCP です。つまり、検証者のクエリに対するオラクルからの応答は線形関数 です。線形 PCP は、SNARK にコンパイルできる証明システムで重要な用途があります。 ${\displaystyle \pi \in \mathbb {F} ^{n}}$${\displaystyle q\in \mathbb {F} ^{n}}$${\displaystyle f(q,\pi )}$

• 数学百科事典におけるホログラフィック証明
• 2008 年、ニューヨーク大学のSubhash Khotによる PCP コースのノート。
• PCP コースノートおよび PCP 定理の歴史 ( Ryan O'DonnellおよびVenkatesan Guruswami著、ワシントン大学、2005 年)。
• 複雑性動物園：PCP