確率的に検証可能な証明

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

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

意味

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

完全性: 任意の $x \in L$ に対して、システムの証明者が生成した証明πが与えられた場合、検証者は少なくともc ( n ) の確率でステートメントを受け入れる。
健全性:任意の $x \notin 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 [r (n), q (n)]$ という略記法は、 $PCP 1, 1/2 [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 [O(1), 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)$ 。

等式表
⁠ ⁠ ${\mathsf {PCP}}[r(n),q(n)]$	0	⁠ ⁠ $O(1)$	⁠ ⁠ $O(\log n)$	⁠ ⁠ $\operatorname {poly} (n)$
0	P	P	P	NP
⁠ ⁠ $O(1)$	P	P	P	NP
⁠ ⁠ $O(\log n)$	P	NP	NP	NP
⁠ ⁠ $\operatorname {poly} (n)$	コーポレーション	MIP = NEXP	ネックス	ネックス

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

リニアPCP

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