PCP定理

同義語:PCP theorem

概要

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$ 近似がない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 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完全 の定義に従う。

PCP 検証者

$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 つが成り立つことをいう。

  1. 完全性. $x\in L$ なら、ある $\pi$ をすべての $R$ で受理する。
  2. 健全性. $x\notin L$ なら、どの $\pi$ についても、一様な $R$ で受理する確率は $1/2$ 以下である。
    ある定数 $c$ について $L$ が $(cr+c,\ cq+c)$ 検証者をもつとき、$L\in\mathrm{PCP}[r,q]$ と書く。

読む位置は $x$ と $R$ だけで決まり、読んだ値によらない。位置は 2 進で書くので、$\pi$ は指数的に長くてもよい。$r=0$ の検証者は乱数なしで $q(n)$ ビットを読むので、$\mathrm{PCP}[0,\mathrm{poly}]=\mathrm{NP}$ である。

PCP定理

$\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) $\mathrm{NP}\subset\mathrm{PCP}[\log n,1]$。
  • (b) ある $q\in\mathbb{N}$ と $\rho<1$ について、$\rho$-GAP $q$CSP は NP困難である。
  • (c) ある $\rho<1$ について、$\rho$-GAP 3SAT は NP困難である。
検証者を制約の列と読む

(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$ 個以上の節を充足する割り当てを出す多項式時間の算法をいう。

MAX-3SAT の近似困難性

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 の還元はギャップを作らない

1 節だけ偽になる論理式

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 が示した。

Håstad の定理

どの $\varepsilon>0$ についても、MAX-3SAT に多項式時間の $(7/8+\varepsilon)$ 近似があれば P $=$ NP である。さらに、どの $\varepsilon>0$ についても $\mathrm{NP}\subset\mathrm{PCP}_{1,7/8+\varepsilon}[\log n,3]$ で、検証者は $3$ ビットの選言だけを確かめるようにできる(AB07 Theorem 19.5・Corollary 19.6、pp. 387–388、WS11 Theorem 16.23、p. 424。添字は完全性と健全性の定数)。

この記事では 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)。

指数長の証明の PCP

読むビット数が定数で済む仕組みを、指数長の証明を許した場合に完全に示す。証明を線形関数の値の表にして、誤りを全体に広げる。
$\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$ 近い。

Fourier 係数の 3 乗和

$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$

指数長の証明の PCP

$\mathrm{NP}\subset\mathrm{PCP}[\mathrm{poly}(n),1]$ である(AB07 Theorem 18.21、p. 363)。

2 次方程式系の解を表に書く

要点:解 $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)。

Dinur の証明の筋

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)。

ギャップの倍増(Dinur)

ある有限集合 $\Sigma_0$ があって、どの有限集合 $\Sigma$ についても、定数 $C>0$ と $0<\alpha<1$ があり、字母 $\Sigma$ の制約グラフ $G$ から字母 $\Sigma_0$ の制約グラフ $G'$ を多項式時間で作れて、次が成り立つ(Din07 Theorem 4.1、p. 10)。

  1. $G'$ の大きさは $G$ の大きさの $C$ 倍以下である。
  2. $\mathrm{gap}(G)=0$ なら $\mathrm{gap}(G')=0$ である。
  3. $\mathrm{gap}(G')\ge\min(2\,\mathrm{gap}(G),\alpha)$ である。

この記事では thm-pcp-dinur を証明しない。証明は次の $3$ 段からなる(Din07 pp. 5–10、AB07 Lemmas 18.28–18.30、pp. 369–370)。

  1. 前処理. $G$ を、次数が一定で エクスパンダーグラフ である制約グラフに直す。ギャップは定数倍しか減らない。
  2. 増幅. グラフを $t$ 乗する。新しい辺は長さ $t$ の道で、各頂点は距離 $t/2$ 程度以内の頂点の値についての「意見」をもつ。ギャップは $\sqrt t$ の定数倍になる($\mathrm{gap}\le1/t$ の範囲。Din07 Lemma 3.4、p. 8)が、字母は定数のまま大きくなる。この段の証明が中心である。
  3. 合成. 定数の大きさの各制約に 割り当ての検査器(assignment tester)を当てて、大きくなった字母を $\Sigma_0$ に下げる。これは PCP の検証者に、読む変数の値が制約を満たす値に近いことまで確かめる条件を足したもので、制約どうしの整合性を保つためにこの条件が要る(Din07 Definition 3.1・Lemma 3.5、pp. 8–9)。thm-pcp-hadamard と同じ Hadamard 符号の方法で作れる(Din07 p. 2)。ギャップは定数倍しか減らない。
    $t$ を十分大きくとると、$3$ 段を合わせてギャップが $2$ 倍以上になる。
倍増から PCP定理へ

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-78NP困難性
反例の確かめ
  • $2$ ビット. 完全性 $1$ の検証者で読むビットが $2$ 以下なら、すべての乱数で受理する証明の存在は、$2$ 変数の制約の連言、すなわち幅 $2$ の CNF の充足可能性である。これは多項式時間で判定できる(Cook–Levinの定理 の命題「2SAT は P に属する」)。よってこのような言語は P に属し、$\mathrm{NP}$ を含まない。
  • 乱数 $O(1)$. 読まれうる位置は定数個なので、証明は定数通りである。全部を試すと P に属する。
  • 乱数が多項式. $\mathrm{PCP}[\mathrm{poly},1]=\mathrm{NEXP}$ である(AB07 Theorem 18.4、p. 354)。時間階層定理により NP $\ne$ NEXP である(AB07 §3.3、p. 67)。prop-pcp-easy の議論では、乱数を全部試すのに指数時間かかる。
  • 線形の検査. $3$ ビットの和の式の連立の充足可能性は Gauss の消去法で判定できるので、完全性 $1$ では P に属する。Håstad の $3$ ビットの線形の検証者の完全性が $1-\varepsilon$ であるのはこのためである(AB07 p. 388)。
  • 健全性 $1$. 定数 $1$ を返す検証者は、すべての言語の検証者になる。
  • $\rho<7/8$. prop-pcp-78 により $\mathrm{val}\le\rho$ の例がないので、$f$ が存在すれば $L$ はすべての語からなる。

文献

定理は 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 による。

関連項目

参考文献

[1]
[2]
Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM, 2007, Article 12。番号と頁は ECCC Report No. 46 (2005) のもの:序 pp. 1–2、Definition 2.1 pp. 3–4、Proposition 2.1 p. 4、§3 pp. 5–10、Lemma 3.4 p. 8、Definition 3.1 pp. 8–9、Lemma 3.5 p. 9、Theorem 4.1 p. 10
[3]
Sanjeev Arora; Boaz Barak, Computational Complexity: A Modern Approach, Web draft(2007-01-08)。刊行版は 2009 年, Cambridge University Press, 2009, 頁は Web draft 2007-01-08 の通し頁:§3.3 p. 67、Definition 18.1・Theorem 18.2 p. 353、Theorem 18.4 p. 354、Definition 18.9 p. 356、Definitions 18.10–18.11 p. 357、§18.2.4 pp. 358–359、Lemma 18.15 pp. 359–360、§18.3 pp. 361–363、Theorem 18.21 p. 363、Lemmas 18.28–18.30 pp. 369–370、Theorem 19.5 p. 387、Corollary 19.6 p. 388

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する