PCP定理とその証明 (証明概要編)

本記事は

1. PCP定理とその証明 (紹介編)
2. PCP定理とその証明 (準備編)

の続きで, PCP定理の証明の全体像を説明します. 細かい解析などは後の記事で行います. この分野を専門的に学ぶ必要がない限りは本記事まで把握していれば良いと思います. 「エクスパンダー性がどのように効いてくるのか？」などについては以降の記事を読む必要があります.

簡単な復習

これまで, 2-CSPに対して制約グラフと呼ばれる概念を定義しました.

制約グラフ$G = ((V,E),\Sigma,\mathcal{C})$のサイズを
$$ \mathrm{size}(G) = |V|+|E| $$
で定めます ($\Sigma$と$\mathcal{C}$には依存しません).

ステップ1ではUNSATの値をさほど変えずに構造グラフを正則エクスパンダーに変換できることを示しました.

以後, 簡単のためにグラフに対する諸概念を制約グラフに対して当てはめて呼びます. 例えば「$d$-正則制約グラフ」と言った場合, その構造グラフ$(V,E)$の正則性を意味します.

UNSATの倍化

定理1はUNSATの値を倍化するという次の定理から証明できます.

端的に言えば, 制約グラフをUNSAT値を倍になるよう効率的に変換できるという定理です. 充足不能な制約グラフ$G$は常に$\mathrm{UNSAT}(G) \ge 1/|E|$が成り立つので, ギャップ増幅定理を$O(\log(|E|))$回だけ適用すれば$\mathrm{UNSAT}(G)\ge \alpha$にできます.

定理3の証明は次の三つの構成要素からなります:

1. 構造グラフをスパースかつエクスパンダーにする
2. ギャップ増幅
3. アルファベット削減

前回の記事では一つ目について解説しました. 本記事では残りの二つについて解説します.

ギャップ増幅補題

定理3の証明へのチャレンジとして, 次の方針を考えてみます.

方針: アルファベットの増大

アルファベットサイズを(元の制約グラフのサイズに依存して)十分大きくすることが許されるならば, ギャップ増幅は容易です. 元の制約グラフを$G=((V,E),\Sigma,\mathcal{C})$とします. $G'=((V,E'),\Sigma',\mathcal{C}')$を以下で定めます:

• 変換後のグラフ$(V,E')$を$V$上の完全グラフとします.
• 変換後のアルファベットを$\Sigma'=\Sigma^V$とします. 割り当て$\sigma \colon V \to \Sigma'$と頂点$u\in V$に対し, $\sigma(u) \in \Sigma'$は関数$\sigma(u) \colon V \to \Sigma$とみなします.
• 変換後の制約$\mathcal{C}'$を定義します. 割り当て$\sigma \colon V \to \Sigma'$は次の条件を満たすとき, $G'$の辺$e=\{u,v\}$における制約を満たすとします: 関数として$\sigma(u)=\sigma(v)$であり, さらに$\sigma(u)\colon V \to \Sigma$は元の制約グラフの$\mathcal{C}$の全ての制約を満たす.

元の制約グラフ$G$が$\UNSAT(G)=0$ならば, その充足割り当てを使って$G'$の充足割り当てが構成できるため$\UNSAT(G')=0$です. 一方で$\UNSAT(G)>0$ならば, どの割り当てを使っても全ての辺が充足されないため$\UNSAT(G')=1$となります. 完全グラフに変換する方法は確かにギャップを増幅しています.

しかしこの構成は定理3の証明にはなりえません. というのも, この構成によって得られる制約グラフのアルファベット$\Sigma'=\Sigma^V$はその要素数が元のグラフに依存してしまうからです. 定理3では, 元のグラフが如何に大きくても同じアルファベット$\Sigma_0$上の制約グラフに変換することが要請されていることに注意が必要です.

制約グラフの冪乗

ギャップ増幅ではグラフの冪乗と呼ばれる操作によって与えられる制約グラフを考えます. 一般にグラフの冪乗と言えばそのグラフの隣接行列の冪乗を指す概念です. グラフ$G = (V,E)$および$\ell\in \mathbb{Z}_{\ge 0}$に対し, $\ell+1$個の頂点からなる列$(u_0,u_1,\dots,u_\ell)$は全ての$u_i,u_{i+1}$が辺をなすときに$u_0$から$u_\ell$への$\ell$-ウォークと呼び, 特に二頂点$u_0,u_\ell$をそれぞれ始点,終点と呼びます. ここでは$(u_0,\dots,u_\ell)$は順序付きのタプルですが, グラフは無向グラフなので順序を反転させたタプル$(u_\ell,\dots,u_0)$もまた$u_\ell$から$u_0$への$\ell$-ウォークになっています.

冪乗グラフ$G^\ell$とは全ての長さ$\ell$のウォークの端点間に辺を追加して得られるグラフです. 同じ二頂点間に長さ$t$のウォークが二通り以上存在する場合はその個数(逆向きのウォークは数えない)分だけ多重辺にします. 元のグラフ$G$が$d$-正則ならば$G^\ell$は$d^\ell$-正則です (ここでは多重辺はその分だけ次数をカウントしているため, 隣接点がちょうど$d^\ell$個あるわけではないことに注意).
グラフ$G$と$G^2$の例. 太線は2本の多重辺を持つことを意味する.

制約グラフに対する冪乗操作を定めるためにいくつか準備をします. $d$-正則な制約グラフ$G$を考え, その頂点集合$V$に番号付けをして$V=\{v_1,\dots,v_n\}$とし, $V$に全順序をつけます (このときの順序はどのようなものでも構いません). このとき, 各頂点$u$の隣接点集合$N_G(u)$にも頂点番号に基づいて順序が定まります. こうすることで, 頂点$u$の$j$番目の隣接点を定めることができます. 同様に$G^\ell$に対しても$u$の隣接頂点集合$N_{G^\ell}(u)$に順序がつきます.

次の定義がこの記事(ひいてはDinur PCPの理解)における最も重要な概念ですので, 長いですが確実に理解しましょう.

初見だとイメージがわかりずらいかもしれませんが, 次の図が参考になると思います.
頂点$u$に割り当てられた値$a$は$\Gamma(u)=N_{G^{\lceil t/2 \rceil}}(u)$の各頂点に$\Sigma$の元を割り当てる関数とみなす (上). それぞれ頂点$u,v$を中心とした距離$\lceil t/2 \rceil$にある二つの円を考え, それらの間にある$G$の辺に対応する制約を全て満たしていれば, $(a,b)$は$e'=\{u,v\}$に対応する制約を満たす.

元の制約グラフが$\UNSAT(G)=0$ならば, $\UNSAT(G^t)=0$です. 実際, $G$の充足割り当ての一つを$\sigma\colon V \to \Sigma$としたときに, $\vec{\sigma}(u)_v = \sigma(v)$なる任意の$\vec{\sigma}$を考えると球内の任意の二頂点間の元の制約が満たされるため, $\UNSAT(G^t)=0$となることがわかります.

では$\UNSAT(G)>0$であった時はどうなるでしょうか? 元の制約グラフ$G$が自己ループを持つ正則エクスパンダーならば$\UNSAT(G^t)$が増幅することが示せます.

アルファベット削減

パラメータ$t\in\Nat$を$2/\beta$くらいにとっておけば補題4より$\UNSAT(G^t)\ge 2\UNSAT(G)$となります. 一見するとこれで定理3を示せていそうに見えますが,　$G^t$のアルファベット$\Sigma'$はその要素数が元のアルファベット$\Sigma$に依存してしまうため証明になっていません. そこでアルファベットサイズを$G$に依存しない定数まで削減する必要があります. このパートをアルファベット削減(alphabet reduction)と言います.

ここではアルファベット$\Sigma_0$と定数$\beta,c$は与えられた制約グラフ$G$に依存しないことに注意してください.
補題5は当時すでに知られていた手法から(専門家にとっては)容易に証明できる内容なのですが, その証明には誤り訂正符号やassignment tester (PCP of proxity) といった概念を要するので初学者にとっては厳しい道のりになるでしょう.

各種補題の仮定の下でのPCP定理の証明

エクスパンダー化(補題2), ギャップ増幅補題(補題4), アルファベット削減補題(補題5)の仮定の下で定理3を証明します. 定理3がPCP定理(定理1)を導出することは既に示してありますので, これらの補題からPCP定理が導出できます.