PCP定理(PCP theorem)とは、NP のどの言語も、乱数 $O(\log n)$ ビットを使い証明の定数個のビットだけを読む多項式時間の検証者で検査できる、という定理である。ここで正しい主張には確率 $1$ で受理する証明があり、誤った主張ではどの証明も確率 $1/2$ 以下でしか受理されない。これは、ある $\rho<1$ について 3CNF が充足可能か充足できる節の割合が $\rho$ 以下かの区別が NP困難であることと同値である。この形から、$\mathrm{P}\ne\mathrm{NP}$ のもとで MAX-3SAT にはある定数 $\rho_0<1$ の多項式時間 $\rho_0$ 近似がない。
前提知識: NP完全, Cook–Levinの定理, 連言標準形
PCP定理(PCP theorem)は、NP のどの言語についても、証明の書き方を変えると、多項式時間の検証者が $O(\log n)$ ビットの乱数で選んだ定数個のビットだけを読み、正しい主張には確率 $1$ で受理する証明があり、誤った主張ではどの証明も確率 $1/2$ 以下でしか受理されない形にできる、という定理である。PCP は probabilistically checkable proofs(確率的に検査できる証明)の略である。
通常の NP の証明書は全部読まないと検証できない。1 ビットの誤りが結論を変えうるからである。PCP定理は、誤りが証明全体に広がるように書き直せることを主張する。検証者が乱数を使う点は、証明者と検証者がやりとりする対話証明と共通する。対話のやりとりで、主張が正しいこと以外の情報を検証者に渡さないようにする仕組みは ゼロ知識証明 で扱う。
同じ定理は最適化の言葉でも述べられる。ある定数 $\rho<1$ について、3CNF の論理式が充足可能か、どの割り当てでも節の $\rho$ 以下しか充足できないかを区別することは NP困難である。したがって P $\ne$ NP なら、MAX-3SAT には $1$ に近い定数倍の多項式時間近似がない。Cook–Levinの定理 の還元はこの性質をもたない(ex-pcp-cook-levin)。
この記事では、PCP の定義を置き、証明の見方と近似の見方の同値を完全に証明する。定理の本体の証明は長いので、指数長の証明を許した弱い形 $\mathrm{NP}\subset\mathrm{PCP}[\mathrm{poly},1]$ を完全に示し、本体は Dinur の証明の筋を、どこまで証明しどこに依存するかを明示して述べる。
言語はすべて $\{0,1\}^*$ の部分集合とする。P・NP・多項式時間還元は NP完全 の定義に従う。
$r,q\colon\mathbb{N}\to\mathbb{N}$ とする。$(r,q)$ 検証者 とは、入力 $x$(長さ $n$)と 乱数 $R\in\{0,1\}^{r(n)}$ から、$k\le q(n)$ 個の位置 $i_1,\dots,i_k$ と述語 $C\colon\{0,1\}^k\to\{0,1\}$ を多項式時間で計算する機械 $V$ である。語 $\pi$(証明)の $i$ ビット目を $\pi[i]$ と書き(長さを超える位置の値は $0$ とする)、$C(\pi[i_1],\dots,\pi[i_k])=1$ のとき $V$ は乱数 $R$ で $\pi$ を 受理 するという。
$V$ が言語 $L$ の検証者であるとは、次の 2 つが成り立つことをいう。
読む位置は $x$ と $R$ だけで決まり、読んだ値によらない。位置は 2 進で書くので、$\pi$ は指数的に長くてもよい。$r=0$ の検証者は乱数なしで $q(n)$ ビットを読むので、$\mathrm{PCP}[0,\mathrm{poly}]=\mathrm{NP}$ である。
$\mathrm{NP}=\mathrm{PCP}[\log n,1]$ である。すなわち、NP の言語はどれも、乱数 $O(\log n)$ ビット、読むビット数 $O(1)$ の検証者をもち、逆もいえる(AB07 Definition 18.1・Theorem 18.2、p. 353)。
$\mathrm{PCP}[\log n,1]\subset\mathrm{NP}$ の向きは易しい。
$\mathrm{PCP}[\log n,1]\subset\mathrm{NP}$ である。
$V$ を $(r,q)$ 検証者とし、$r=O(\log n)$、$q=O(1)$ とする。乱数は $2^{r}$ 通りで $n$ の多項式個だから、読まれうる位置は全部で $q2^{r}$ 個以下である。証明書を、これらの位置の値の列とする。各 $R$ について $V$ を走らせ、すべてで受理することを多項式時間で確かめる。$x\in L$ なら完全性からこの証明書がある。$x\notin L$ なら、どの $\pi$ でも受理の確率は $1/2$ 以下で $1$ 未満なので、受理しない $R$ がある。$\square$
$q\ge1$ とする。$q$CSP の例 $\varphi$ とは、$\{0,1\}$ 値の変数 $u_1,\dots,u_n$ の上の 制約 $\varphi_1,\dots,\varphi_m$ の列で、各 $\varphi_i$ は $1$ 個以上 $q$ 個以下の変数を指定し、その値の関数として $\{0,1\}$ の値をとるものである。$\varphi$ の 値 を
$$
\mathrm{val}(\varphi):=\max_{u\in\{0,1\}^n}\frac{\#\{i:\varphi_i(u)=1\}}{m}
$$
と定める。$\mathrm{val}(\varphi)=1$ が充足可能にあたる。幅 $3$ 以下の CNF の論理式は $3$CSP の例である(AB07 Definition 18.11、p. 357)。
$\rho\in(0,1)$ とする。$\rho$-GAP $q$CSP が NP困難 であるとは、どの $L\in\mathrm{NP}$ にも多項式時間で計算できる写像 $f$ があって、$x\in L$ なら $\mathrm{val}(f(x))=1$、$x\notin L$ なら $\mathrm{val}(f(x))\le\rho$ となることをいう。$f(x)$ が 3CNF に限られる場合を $\rho$-GAP 3SAT が NP困難 という(AB07 Definitions 18.9–18.10、pp. 356–357、p. 358)。
変数の値の範囲を一般の有限集合にし、使える制約の種類を固定したときの充足可能性の判定の計算量(多項式時間か NP完全かの二分)は 制約充足問題 で扱う。
次の 3 条件は同値である。
(a)$\Rightarrow$(b).3SAT の $(r,q)$ 検証者 $V$ をとる($r=O(\log n)$、$q$ は定数)。入力 $\psi$ に対し、乱数 $R$ ごとに、読む位置を変数とする制約 $\varphi_R:=C$ を作る。乱数は多項式個で、$V$ は多項式時間なので、$\varphi=(\varphi_R)_R$ は多項式時間で書き出せる(使われる位置を $1,2,\dots$ に番号づけし直す。どの位置も読まない $R$ には、値が $C$ である $1$ 変数の制約を当てる)。$u$ を証明と見ると、$\varphi_R(u)=1$ は「乱数 $R$ で受理する」ことなので、$\mathrm{val}(\varphi)$ は受理確率の最大値である。よって $\psi\in$ 3SAT なら $\mathrm{val}(\varphi)=1$、そうでなければ $\mathrm{val}(\varphi)\le1/2$ である。任意の $L\in\mathrm{NP}$ は 3SAT に多項式時間還元できる(Cook–Levinの定理)ので、合成すると $1/2$-GAP $q$CSP は NP困難である。
(b)$\Rightarrow$(c).$\varphi$ を $q$CSP の例とし、$m$ を制約の個数とする。各制約 $\varphi_i$ について、その変数への値の割り当てのうち $\varphi_i$ を偽にするもの $1$ つごとに、「その割り当てではない」という幅 $q$ 以下の節を作る。節は $2^q$ 個以下で、それらの連言は $\varphi_i$ と同値である。次に Cook–Levinの定理 の命題「SAT から 3SAT への還元」の分割を各節に当て、節ごとに別の新しい変数を使って、幅 $3$ 以下の節 $q$ 個以下に置き換える。この分割では、元の節が真なら新しい変数の値を選んで全部の節を真にでき、元の節が偽ならどう選んでも少なくとも $1$ つの節が偽である。得られた 3CNF を $\psi$ とする。節の個数を $M$ とすると $M\le Km$($K:=q2^q$)である。
$\mathrm{val}(\varphi)=1$ なら $\mathrm{val}(\psi)=1$ である。$\mathrm{val}(\varphi)\le\rho$ とする。$\psi$ の任意の割り当てを元の変数に制限した $u$ は、$(1-\rho)m$ 個以上の制約を偽にする。偽の制約 $\varphi_i$ ごとに偽の節があり、その分割から偽の節が少なくとも $1$ つ出る。制約ごとに節は別なので、偽の節は $(1-\rho)m\ge(1-\rho)M/K$ 個以上ある。よって $\mathrm{val}(\psi)\le1-(1-\rho)/K<1$ である。$q$ は定数なので $K$ も定数で、$\varphi\mapsto\psi$ は多項式時間である。
(c)$\Rightarrow$(a).$L\in\mathrm{NP}$ とし、$f$ を (c) の写像とする。入力 $x$ から $\psi=f(x)$(節 $D_0,\dots,D_{m-1}$、$m\ge1$)を作る。$2^k\ge2m$ となる最小の $k$ をとる。$f$ は多項式時間なので $k=O(\log n)$ である。1 回の検査は次のとおりとする。乱数 $R\in\{0,\dots,2^k-1\}$ に対し $D_{R\bmod m}$ の変数($3$ 個以下)を証明から読み、節が真なら受理する。証明は変数の割り当てと見る。
$x\in L$ なら $\psi$ を充足する割り当てはどの $R$ でも受理される。$x\notin L$ なら、どの割り当てでも偽の節が $(1-\rho)m$ 個以上ある。各節が選ばれる確率は少なくとも $\lfloor2^k/m\rfloor/2^k\ge1/m-2^{-k}\ge1/(2m)$ なので、拒否の確率は $\delta:=(1-\rho)/2$ 以上である。
検査を独立に $t:=\lceil1/\delta\rceil$ 回行い、すべて通れば受理する。$x\notin L$ のときの受理確率は $(1-\delta)^t\le e^{-1}<1/2$ である。乱数は $tk=O(\log n)$ ビット、読むビットは $3t=O(1)$ で、$V$ は $L$ の検証者である。$\square$
これは AB07 §18.2.4(pp. 358–359)と Lemma 18.15(pp. 359–360)の議論である。対応は次のとおりである(AB07 p. 359)。
| 検証者 | CSP の例 |
|---|---|
| 証明 $\pi$ | 変数の割り当て $u$ |
| 証明の長さ | 変数の個数 $n$ |
| 読むビット数 $q$ | 制約の変数の個数 $q$ |
| 乱数 $r$ ビット | 制約の個数の対数 $\log_2m$ |
| 健全性の定数 | 誤った主張の例の $\mathrm{val}$ の上界 |
MAX-3SAT は、3CNF $\psi$ を入力として充足する節の個数を最大にする問題である。多項式時間の $\rho$ 近似 とは、節が $m$ 個の $\psi$ に対し $\rho\,\mathrm{val}(\psi)m$ 個以上の節を充足する割り当てを出す多項式時間の算法をいう。
PCP定理が成り立つので、ある定数 $\rho_0<1$ があって、MAX-3SAT に多項式時間の $\rho_0$ 近似があれば P $=$ NP である。
thm-pcp-equivalence の (c) の $\rho$ に対し $\rho_0:=(1+\rho)/2\in(\rho,1)$ とする。$L\in\mathrm{NP}$、$\psi=f(x)$ とし、$\rho_0$ 近似の出力が充足する節の個数を $s$ とする。$x\in L$ なら $s\ge\rho_0m>\rho m$ である。$x\notin L$ なら $s\le\mathrm{val}(\psi)m\le\rho m$ である。$s>\rho m$ かどうかで $L$ を多項式時間で判定できる。$\square$
Cook–Levinの定理 の論理式 $\varphi_w$ は (U)・(B)・(S)・(L)・(A) の節の連言であった。$w\notin L$ でも、たとえば空の証明書 $y$ をとり、入力 $w\#y$ の実際の計算の表から割り当てを作ると、(U)・(B)・(S)・(L) はすべて真で、偽になるのは (A) の $1$ 節だけである。よって、節の個数を $m$ とすると $\mathrm{val}(\varphi_w)\ge1-1/m$ である。幅を $3$ に下げても同じである。真である長い節の分割は、Cook–Levinの定理 の命題「SAT から 3SAT への還元」のとおり新しい変数を選んで全部真にできる。(A) の節 $\{\ell_1,\dots,\ell_k\}$ の分割 $\{\ell_1,\ell_2,z_1\},\{\neg z_1,\ell_3,z_2\},\dots$ では、新しい変数をすべて真にすると、偽の節は最後の $1$ 個だけになる。
これは計算の表が頑健でないことを示している。表の $1$ か所の誤りが受理と拒否を変え、節はその $1$ か所しか見ない(AB07 p. 356)。PCP定理の本質は、この $1/m$ の差を定数まで広げる点にある。
$\rho$ をどこまで下げられるかは問題ごとに異なる。MAX-3SAT では $7/8$ が境目である。
どの節もちょうど $3$ 個の相異なる変数のリテラルからなる 3CNF $\psi$(節 $m$ 個)について、$7m/8$ 個以上の節を充足する割り当てが存在し、多項式時間で求められる。とくに $\mathrm{val}(\psi)\ge7/8$ である。
一様な割り当てでは、$1$ 節が偽になる確率は $1/8$ なので、充足する節の個数の期待値は $7m/8$ である。変数を順に見て、それまでに固定した値のもとでの条件付き期待値が大きいほうの値に固定する。条件付き期待値は、節ごとの残りの変数の個数から直接計算でき、2 つの値の平均が固定前の条件付き期待値なので、減らない。全部固定すると、充足する節の個数は $7m/8$ 以上である。$\square$
したがって、このような論理式に限ると $\mathrm{val}\le\rho$($\rho<7/8$)となる例は存在しない。この定数が最良であることを Håstad が示した。
この記事では thm-pcp-hastad を証明しない。
PCP定理の帰結は MAX-3SAT に限らない。次の還元で 独立集合 に移る。
3CNF $\psi$(節 $m$ 個)から、節 $i$ とそのリテラル $\ell$ の組 $(i,\ell)$ を頂点とし、同じ節の 2 頂点の間と、$x,\neg x$ の組の間に辺を引いたグラフ $G_\psi$ を作る。$G_\psi$ の独立集合の最大の大きさは $\mathrm{val}(\psi)m$ である。したがって、最大独立集合に多項式時間の $\rho$ 近似があれば MAX-3SAT にも $\rho$ 近似があり、$\rho\ge\rho_0$ なら P $=$ NP である。
要点:独立集合は各節から矛盾しないリテラルを高々 $1$ つ選ぶことにあたる。
割り当てが $t$ 節を充足するとき、各節から真のリテラルを $1$ つ選ぶと、$t$ 個の頂点の独立集合になる。逆に独立集合 $S$ は、同じ節の頂点を $2$ つ含まず、$x,\neg x$ を同時に含まない。$S$ のリテラルをすべて真にする割り当て(残りの変数は任意)は $|S|$ 個の節を充足する。この変換は多項式時間で、$\rho$ 近似の出力 $|S|\ge\rho\,\mathrm{val}(\psi)m$ を割り当てに移せる。$\square$
最大独立集合については、頂点数 $n$ のグラフに対し、ある $\delta>0$ で最大値の $n^{-\delta}$ 倍の大きさの独立集合を求める多項式時間の算法があれば P $=$ NP であることも知られている(AB07 §18.3、pp. 361–363)。
読むビット数が定数で済む仕組みを、指数長の証明を許した場合に完全に示す。証明を線形関数の値の表にして、誤りを全体に広げる。
$\mathbb{F}_2$ 上のベクトル $a,x$ の内積を $\langle a,x\rangle$ と書く。関数 $f\colon\mathbb{F}_2^n\to\mathbb{F}_2$ が $\langle a,\cdot\rangle$ に $\delta$ 近い とは、一様な $x$ で $\Pr[f(x)\ne\langle a,x\rangle]\le\delta$ となることをいう。$a\in\mathbb{F}_2^n$ に関数 $\langle a,\cdot\rangle$ の値の表(長さ $2^n$)を対応させる符号を Walsh–Hadamard 符号 という。$0$ でない線形関数はちょうど半分の点で $1$ をとるので、相異なる $2$ つの語はちょうど半分の位置で異なる。これは長さ $2^n$、次元 $n$、最小距離 $2^{n-1}$ の 線形符号 である。
$f\colon\mathbb{F}_2^n\to\mathbb{F}_2$、$0\le\delta\le1/2$ とする。一様で独立な $x,y$ について $\Pr[f(x)+f(y)=f(x+y)]\ge1-\delta$ なら、$f$ はある $\langle a,\cdot\rangle$ に $\delta$ 近い。
$F:=(-1)^{f}$、$\chi_a(x):=(-1)^{\langle a,x\rangle}$ とする。$(\chi_a)_a$ は一様分布の内積で正規直交基底なので、$F=\sum_a\widehat F(a)\chi_a$、$\sum_a\widehat F(a)^2=1$ である。直交性から
$$
\mathbb{E}_{x,y}[F(x)F(y)F(x+y)]=\sum_{a}\widehat F(a)^3.
$$
検査が通る確率は $(1+\mathbb{E}[F(x)F(y)F(x+y)])/2$ なので、$\sum_a\widehat F(a)^3\ge1-2\delta$ である。$\max_a\widehat F(a)\cdot\sum_a\widehat F(a)^2\ge\sum_a\widehat F(a)^3$ より、ある $a$ で $\widehat F(a)\ge1-2\delta$ である。$\widehat F(a)=1-2\Pr[f(x)\ne\langle a,x\rangle]$ なので、$\Pr[f(x)\ne\langle a,x\rangle]\le\delta$ である。$\square$
$\mathrm{NP}\subset\mathrm{PCP}[\mathrm{poly}(n),1]$ である(AB07 Theorem 18.21、p. 363)。
要点:解 $u$ の表 $f=\langle u,\cdot\rangle$ と $u\otimes u$ の表 $g$ を証明とし、線形性・両者の整合性・方程式のランダムな和を検査する。
2 次方程式系. 3CNF の各節 $\ell_1\lor\ell_2\lor\ell_3$ に新しい変数 $v$ を足し、$\mathbb{F}_2$ 上の方程式 $v=(1+\ell_1)(1+\ell_2)$、$v(1+\ell_3)=0$ に置き換える。$u_i^2=u_i$ を使うと、3SAT は、$n\times n$ 行列 $A_k$ と $b_k\in\mathbb{F}_2$ に対し $\langle A_k,u\otimes u\rangle=b_k$($k=1,\dots,m$)の解 $u\in\mathbb{F}_2^n$ の存在に還元される。ここで $u\otimes u=(u_iu_j)_{i,j}$ で、行列の内積は成分ごとの和である。
検証者. 証明は $f\colon\mathbb{F}_2^n\to\mathbb{F}_2$ と $g\colon\mathbb{F}_2^{n\times n}\to\mathbb{F}_2$ の値の表とする。$h$ の $v$ での 復号 を、新しい一様な $t$ で $D_h(v):=h(v+t)+h(t)$ とする。1 回の検査は、次の全部を独立な乱数で行う。(1) $f$ と $g$ の線形性の検査。(2) 一様な $r,s\in\mathbb{F}_2^n$ で $D_f(r)D_f(s)=D_g(r\otimes s)$ を確かめる。(3) 一様な $z\in\mathbb{F}_2^m$ で $D_g(\sum_kz_kA_k)=\sum_kz_kb_k$ を確かめる。読むのは $3+3+6+2=14$ ビットである。検査を $100$ 回くり返す。
完全性. 解 $u$ に対し $f=\langle u,\cdot\rangle$、$g=\langle u\otimes u,\cdot\rangle$ とすると、線形なので復号は誤らず、$\langle u,r\rangle\langle u,s\rangle=\langle u\otimes u,r\otimes s\rangle$ からどの検査も通る。
健全性. $\delta=1/100$ とし、解がないとする。$f$ か $g$ が線形関数に $\delta$ 近くなければ、lem-pcp-blr から (1) は確率 $\delta$ より大きく拒否する。そうでないとき、$f$ は $\langle u,\cdot\rangle$ に、$g$ は $\langle W,\cdot\rangle$ に $\delta$ 近い。固定した $v$ で $v+t$ も $t$ も一様なので、復号が誤る確率は $2\delta$ 以下である。
$W\ne U:=u\otimes u$ のとき、$(W-U)s\ne0$ の確率は $1/2$ 以上で、そのとき $r^{\mathsf T}(W-U)s\ne0$ の確率は $1/2$ である。復号の誤りが $3$ 回で $6\delta$ 以下なので、(2) の拒否の確率は $1/4-6\delta=0.19$ 以上である。$W=U$ のとき、解がないので $\langle A_k,U\rangle\ne b_k$ となる $k$ があり、$z$ の $1$ 次式 $\sum_kz_k(\langle A_k,U\rangle+b_k)$ は $0$ でない。よってこれは確率 $1/2$ で $1$ で、(3) の拒否の確率は $1/2-2\delta=0.48$ 以上である。
どの場合も $1$ 回の検査は確率 $1/100$ 以上で拒否するので、$100$ 回すべて通る確率は $0.99^{100}<1/2$ である。乱数は多項式ビット、読むビットは $1400$ である。任意の $L\in\mathrm{NP}$ は 3SAT に還元できる。$\square$
thm-pcp-main との違いは乱数の長さである。$\mathrm{poly}(n)$ ビットの乱数は、指数長の証明の位置を選ぶのに使われる。しかし入力の大きさが定数の場合には指数長でも定数なので、同じ Hadamard 符号の方法で作る検査器は Dinur の証明の中で部品として使える(Din07 p. 2)。
thm-pcp-main の難しい向きは、thm-pcp-equivalence により、ギャップを作る還元を与えればよい。元の証明は代数的で、低次多項式の検査などを組み合わせる(Din07 p. 1)。Dinur の証明は、$1/m$ の小さなギャップから始め、ギャップを $2$ 倍にする操作を $\log m$ 回くり返す。
制約グラフ $G$ とは、グラフ $(V,E)$(ループと多重辺を許す)、有限集合 $\Sigma$(字母)、各辺 $e$ の制約 $c_e\colon\Sigma^2\to\{0,1\}$ の組である。割り当て $\sigma\colon V\to\Sigma$ が充足する辺の割合の最大値を $\mathrm{val}(G)$ とし、$\mathrm{gap}(G):=1-\mathrm{val}(G)$ を ギャップ という。$G$ の大きさを $|V|+|E||\Sigma|^2$ の定数倍で測る(Din07 Definition 2.1、pp. 3–4)。
ある有限集合 $\Sigma_0$ があって、どの有限集合 $\Sigma$ についても、定数 $C>0$ と $0<\alpha<1$ があり、字母 $\Sigma$ の制約グラフ $G$ から字母 $\Sigma_0$ の制約グラフ $G'$ を多項式時間で作れて、次が成り立つ(Din07 Theorem 4.1、p. 10)。
この記事では thm-pcp-dinur を証明しない。証明は次の $3$ 段からなる(Din07 pp. 5–10、AB07 Lemmas 18.28–18.30、pp. 369–370)。
thm-pcp-dinur を認めると thm-pcp-main が成り立つ。
prop-pcp-easy と thm-pcp-equivalence から、(b) を示せばよい。3CNF の各節に頂点を置き、字母を $\{1,\dots,7\}$ として、節を充足する変数の値の組($7$ 通り以下)を字母に対応させ、変数を共有する節の間の辺に一致の制約を置き、各頂点に常に真の制約のループを足す。論理式が充足可能であることと $\mathrm{gap}=0$ は同値で、3SAT は $\mathrm{gap}(G_0)=0$ の判定に還元される(Din07 Proposition 2.1、p. 4)。
thm-pcp-dinur を $G_0$ に当て、続けて $\Sigma=\Sigma_0$ の場合を当て続けて $G_1,G_2,\dots$ を作る。定数は $2$ 種類の $\Sigma$ のものの大きいほうの $C$、小さいほうの $\alpha$ をとる。$k:=\lceil\log_2|E(G_0)|\rceil+1$ とすると、$G_k$ の大きさは $C^k=|E(G_0)|^{O(1)}$ 倍以下で、多項式時間で書き出せる。$\mathrm{gap}(G_0)=0$ なら $\mathrm{gap}(G_k)=0$ である。$\mathrm{gap}(G_0)>0$ なら $\mathrm{gap}(G_0)\ge1/|E(G_0)|$ で、帰納法により $\mathrm{gap}(G_i)\ge\min(2^i\mathrm{gap}(G_0),\alpha)$ なので、$\mathrm{gap}(G_k)\ge\alpha$ である。
最後に、$\Sigma_0$ の各元を $b:=\lceil\log_2|\Sigma_0|\rceil$ ビットで表す(全射 $\{0,1\}^b\to\Sigma_0$ を固定する)。各辺の制約は $2b$ ビットの制約になり、値は変わらない。よって $\rho=1-\alpha$、$q=2b$ で (b) が成り立つ。$\square$
$1$・$2$・$4$ 行目は P $\ne$ NP のもとで述べる。
| 変える条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 読むビットを $2$ 以下に(完全性 $1$) | 2SAT への帰着 | $\mathrm{NP}$ の包含 |
| 乱数を $O(1)$ に | 証明の全探索 | $\mathrm{NP}$ の包含 |
| 乱数を多項式に | $\mathrm{PCP}[\mathrm{poly},1]=\mathrm{NEXP}$ | 逆の包含 $\mathrm{PCP}\subset\mathrm{NP}$ |
| 述語を線形の式に(完全性 $1$、$3$ ビット) | Gauss の消去法 | $\mathrm{NP}$ の包含 |
| 健全性の定数を $1$ に | どの証明も受理する $V$ | 言語の判別 |
| 還元がギャップを作ることを外す | Cook–Levinの定理 の $\varphi_w$ | $\mathrm{val}(\varphi_w)\le\rho$ |
| 幅ちょうど $3$ の 3CNF で $\rho<7/8$ に | prop-pcp-78 | NP困難性 |
定理は AB07 Theorem 18.2 で、$q$ と乱数の定数をはっきり述べた形は WS11 Theorem 16.18(p. 421)である。定理は Arora・Lund・Motwani・Sudan・Szegedy により、Feige・Goldwasser・Lovász・Safra・Szegedy と Arora・Safra の仕事の上に示された(WS11 pp. 444–445)。Dinur の証明は Din07 による。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する