文献あり

PCP定理とその証明 (紹介編)

919

1. はじめに

本記事は計算量理論において非常に重要なPCP定理と呼ばれる定理の紹介をします. 前提知識として「多項式時間アルゴリズム」「クラスNP」「NP完全」といった用語がなんとなくわかっていることを想定しています. 以下に書いたクラスNPのinformalな定義を読んで内容がなんとなくわかるならば大丈夫です:

クラスNP

判定問題$L$は, 以下の性質を満たす決定的多項式時間アルゴリズム$V$と多項式$p\colon\mathbb{N}\to\mathbb{N}$が存在するとき, クラスNPに属すといい, $L\in\mathsf{NP}$と表す:

任意のYesインスタンス$x$に対してある$y\in\{0,1\}^{p(|x|)}$が存在して$V(x,y)=1$.
任意のNoインスタンス$x$と任意の$y\in\{0,1\}^{p(|x|)}$に対し, $V(x,y)=0$.

ここで$|x|$はインスタンス$x$のサイズを表す.
Yesインスタンス$x$に対して上記一つ目の条件を満たす文字列$y\in\{0,1\}^{p(|x|)}$をNP証拠と呼び, アルゴリズム$V$をNP検証者と呼ぶ.

本当はアルゴリズム(とその計算モデル), 計算時間, 判定問題などの用語を定義しないと上の定義は厳密にならないのですが, 一般に普通のC言語などのプログラムを考えてもらえればとりあえず大丈夫です.

直感的にいえば, クラスNPに属す問題は, YesインスタンスがYesたりうる多項式長の証拠を持つ問題といえます. 上記の定義で考えるアルゴリズム$V(x,y)$はインスタンス$x$と$x\in L$であることの「証拠」$y$を受け取ったとき, 本当に$x\in L$であるならば$1$を出力, そうでないならば$0$を出力するアルゴリズムです.

グラフの3彩色

有限な単純無向グラフ$G=(V,E)$に対し, 関数$c\colon V\to\{1,\dots,k\}$であって, 全ての辺$\{u,v\}\in E$に対し$c(u)\neq c(v)$を満たすものを$G$の$k$彩色($k$-coloring)という. グラフ$G$は, $k$彩色が存在するならば$k$彩色可能($k$-colorable)であるという.

「与えられたグラフが$3$彩色可能であるか?」という判定問題を3彩色問題と呼ぶ. この問題はクラスNPに属する. 実際, 任意のYesインスタンス(=3彩色可能なグラフ)$G=(V,E)$に対し, その3彩色$c\colon V\to\{1,2,3\}$を表現する文字列を$y$とすれば, $y$は高々$|V|\cdot \lceil\log_2 3\rceil=O(|V|)$ビットで表現できる. 検証者はグラフ$G=(V,E)$と関数$c\colon V\to\{1,2,3\}$を表す文字列を受け取り, $c$が$G$の3彩色かどうかを判定すれば良い. これは全ての辺の両端点の色を比較するだけなので, $G$のサイズに関する多項式時間で計算できる.

なお, 3彩色の判定問題はNP完全であることが知られている.

充足可能性判定問題(SAT)

$n$変数論理式$\phi(x)$に対し, $\phi(a)=\mathrm{true}$となる割当$a\in\{\mathrm{true},\mathrm{false}\}^n$を充足割当(satisfying assignment)という. 与えられた論理式$\phi$が充足割当を持つかどうかを判定する問題を充足可能性判定問題(SAT; satisfiability problem)という. SATはクラスNPに属する. 実際, 与えられたYesインスタンス$\phi$に対しその充足割当を証拠として持ってくればよい.

特に, 論理式$\phi$が
\begin{align*} \phi(x_1,\dots,x_n) = \bigwedge_{i=1}^n (\ell^1_i\lor \ell^2_i \lor \ell^3_i) \end{align*}
の形で表せるとき, 3CNF形式であるといいます. ここで$\ell^j_i$は適当な変数$x$に対し$\ell^j_i\in\{x,\overline{x}\}$を満たす論理式で, リテラルと呼ばれる.

与えられた3CNF形式に対する充足可能性判定問題は特に3CNFと呼ばれる. この問題はNP完全問題であることが知られている.

制約充足問題(CSP)

グラフの彩色問題とSAT問題の共通の一般化として制約充足問題(CSP; constraint satisfaction problem)というものが知られており, PCP定理の証明においても重要な役割を果たす. パラメータ$k\in\mathbb{N}$に対し, k-CSPと呼ばれる問題では, 有限集合$\Sigma$(アルファベットと呼ばれる)上に値をとる$n$個の変数$x_1,\dots,x_n$上の$m$個の関数$P_1,\dots,P_m\colon \Sigma^n\to\{\mathrm{true},\mathrm{false}\}$が入力として与えられる. ただし各$P_i$は$x_1,\dots,x_n$のうち高々$k$個の変数の値にのみ依存する関数であるとする. kCSPは, 全ての$i\in[m]$に対して$P_i(x_1,\dots,x_n)=\mathrm{true}$を満たすような$x_1,\dots,x_n\in\Sigma^n$が存在するかどうかを判定する問題として定義される. 要するに連立方程式の解が存在するかどうかを判定する問題である.

例えば3彩色問題は$\Sigma=[3]$に対する2-CSPの特殊ケースになる. ここでは, 変数$x_v$は頂点$v$に割り当てられる色を表すとし, 各辺$e=uv\in E$に対して$P_e(x_1,\dots,x_n)$を$x_u=x_v$ならば$\mathrm{true}$, そうでなければ$\mathrm{false}$を返す関数と定義すれば2-CSPとして表現できる. 3CNFは$\Sigma=\{\mathrm{true},\mathrm{false}\}$に対する3CSPの特殊ケースである. 一般にk-CSPを議論する際はアルファベットサイズ$|\Sigma|$と引数の個数$k$は入力長に依存しない定数とする.

1. PCP定理

PCPとはProbabilistic Checkable Proofの略で, 確率的検証可能な証拠のことを表します. 要するにとある良い性質を満たす証拠なのですが, そのような証拠を持つ問題のクラスをクラスPCPと呼びます. PCP定理とは, クラスがクラスNPに一致するということを主張する定理です.

1.1. informalな定義

分かり易さのために, まずinformalにクラスPCPを定義し, 次の節でちゃんとした定義を載せます.

PCP定理(informal)

判定問題$L\in\mathsf{NP}$を考える. 以下を満たす乱択検証アルゴリズム$V$と多項式$p\colon\mathbb{N}\to\mathbb{N}$が存在するとき, $L$はクラスPCPに属すといい, $L\in\mathsf{PCP}$と表す:

任意のYesインスタンス$x$に対し, ある$y\in\{0,1\}^{p(|x|)}$が存在して, $\Pr[V(x,y)=1]=1$
任意のNoインスタンス$x$と文字列$y\in\{0,1\}^{p(|x|)}$に対して$\Pr[V(x,y)=0]\geq 1/2$.
任意のインスタンス$x$と文字列$y\in\{0,1\}^{p(|x|)}$に対し, $V(x,y)$は文字列$y\in\{0,1\}^{p(|x|)}$のうち, たかだか100文字しか見ない.

Yesインスタンス$x$に対して上記の一つ目の条件を満たす文字列$y$をPCPまたはPC証拠と呼び, 乱択アルゴリズム$V$をPCP検証者と呼びます.

クラスNPの定義(定義1)と比較すると, 以下の二つの違いに気づきます:

NP検証者は決定的(すなわちランダムネスを使わない)だったのに対し, PCP検証者はランダムネスを使え, Noインスタンスの拒否確率は$\geq 1/2$であれば良い (従ってこの点においてはNP検証者よりも条件は弱い)
PCP検証者$V$は証明$y\in\{0,1\}^{p(|x|)}$のうち, 100文字しか見ることができない (この点においてはNP検証者よりも非常に強い条件が課されている). なお, 100や$1/2$という定数は分かり易さのため書いているだけであり意味はありません. 問題の入力サイズ$|x|$に依存しない定数であれば良いです.

PCP検証者は証明!FORMULA[101][38383][0]の中で見ることのできる文字数が制限されている. その代わりにサイコロをふることができる. PCP検証者は証明$y$の中で見ることのできる文字数が制限されている. その代わりにサイコロをふることができる.

すなわち, ランダムネスの部分では条件を緩めている一方で証拠へのアクセス回数においては条件を厳しくしています. 一見するとアクセス制限がものすごく強そうな気がするのですが, PCP定理はNP=PCPを主張します.

PCP定理

PCP=NP

3彩色問題の確率的検証

PCP定理の非自明さをさらに納得するために3彩色問題($\mathrm{3COL}$)について考えてみましょう. 3彩色問題とはグラフ$G=(V,E)$が与えられてそれが3彩色可能かどうかを判定する問題でした. この問題のNP証拠としては3彩色$c\colon V\to \{1,2,3\}$をもってくれば良いです. この関数$c$が本当に彩色の条件を満たすかどうかを検証するには全頂点の色を見なければなりませんでした.

ここで, 一様ランダムに辺$\{u,v\}\in E$を選んでその両端点で$c(u)\neq c(v)$ならば受理し, そうでなければ拒否する乱択アルゴリズム$V$を考えてみましょう. この検証者は確かに2頂点の色しか見ておらず, しかも$c$が3彩色だった場合は確率1で受理します. 一方, $c$が彩色でなかった場合は$c(u)=c(v)$となる辺$\{u,v\}$が存在し, このような辺を引き当てた場合のみ$V$は拒否します. しかしそのような辺が1本のみだった場合, $V$の拒否確率は$1/|E|=\Theta(1/|V|^2)$となってしまい, $1/2$からは程遠い値となってしまいます.

では, ランダムに辺を$k$本選んでその中で両端点が同じ色になるものが存在するかどうかによって判定するのはどうでしょうか? この場合, 見る頂点の個数は高々$2k$個であり, Noインスタンスを拒否する確率は$1-(1-1/|E|)^k\approx 1-\exp(-k/|E|)$となり, やはり定数$1/2$からは程遠いです ($k$を増やすとこの確率は定数にできる一方で見る頂点の個数は増えてしまう).

PCP定理によると$\mathrm{3COL}\in\mathsf{PCP}$なので, 実際にPCPを持ちます. 重要なのはPCPの存在性であり, それは先ほど考えたNP証拠の関数$c$と同じであるとは限らないという点です.

1.2. 厳密な定義

ここでは厳密な定義を載せますが, 要するに2.1の内容をちゃんとした形で述べ直しただけなので, 読み飛ばしても大丈夫です.

オラクルアルゴリズム

文字列$z\in\{0,1\}^*$に対し, 計算途中で$z$の文字を参照する(すなわち, 何らかのインデックス$i$に対して$z_i$にアクセスする)ようなアルゴリズム$A$を($z$オラクルを持つ)オラクルアルゴリズムといい, $A^z$で表す. この参照をクエリ(query)と呼ぶ.

関数$q\colon\mathbb{N}\to\mathbb{N}$と入力$x$を受け取るオラクルアルゴリズム$A^z(x)$を考えます. 任意の$x$に対して$A^z(x)$のクエリ回数が高々$q(|x|)$回であるとき, $A^z$のクエリ計算量は高々$q(n)$であるといいます.
乱択オラクルアルゴリズム$A^z$のクエリ計算量は, ありうる全てのランダムネスの中で最も多いときのクエリ回数として定義します.

例えばクラスNPの定義における検証アルゴリズム$V(x,y)$は, $y$をオラクルと見立たとき, オラクルアルゴリズム$V^y(x)$とみなすこともできます. $y$の文字全てを見る可能性があるので, クエリ計算量は最悪ケースで$|y|$です.

クラスPCP

二つの関数$p,r\colon\mathbb{N}\to\mathbb{N}$を考える. 判定問題$L$は, 以下の性質を満たす多項式時間乱択オラクルアルゴリズム$V$と多項式$p\colon\mathbb{N}\to\mathbb{N}$が存在するとき, $\mathrm{PCP}(r,q)$に属すといい, $L\in\mathsf{PCP}(r,q)$と表す:

任意のYesインスタンス$x$に対してある$y\in\{0,1\}^{p(|x|)}$が存在して$\Pr[V^y(x)=1]=1$.
任意のNoインスタンス$x$と任意の$y\in\{0,1\}^{p(|x|)}$に対して$\Pr[V^y(x)=0]\geq 1/2$.
$V$のクエリ計算量は高々$q(|x|)$であり, $V$が使うランダムビットは高々$r(|x|)$ビット.

PCP定理

$\mathsf{PCP}(O(\log n),O(1))=\mathsf{NP}$.

$\mathsf{PCP}(O(\log n),O(1))\subseteq \mathsf{NP}$は自明です. 実際, $r$ビットのランダムネスを使いクエリ計算量$q$のPCP検証者がいた場合, 全てのランダムビットを列挙してそれぞれでPCP検証者を決定的にシミュレーションして出力の多数決をとれば決定的な検証者が作れます. この検証者の計算時間は$2^r\cdot q = 2^{O(\log n)}=\mathrm{poly}(n)$となり確かに多項式時間です.

1.3. 応用

PCP定理を用いると, $\mathsf{P}\neq\mathsf{NP}$の仮定の下で, 多項式時間アルゴリズムによる近似率の限界を証明することができます. 詳しくはこちらのページの4章などを参照してください.

1.4. 背景

大雑把に言えば, 計算量理論の目標とは特定のタスクをこなすのに必要な計算資源の量(時間, メモリ量, 乱択や量子性の有無など)を明らかにすることです. その中でクラスNPのような「答えがあっているかどうかを検証する」というタスクの計算量が注目を集めました. 例えば関数$f$に対して$f(x)$の値を外部のスーパーコンピュータに計算してもらった時に$y$という値が帰ってきたとして, ではそのスーパーコンピュータが信頼できるか(それが本当に正しく$f(x)=y$を満たすのか)を検証するにはどうすれば良いでしょうか?

一つの方法として対話証明という方法があります. これは検証者(=乱択アルゴリズム)のほかに証明者(例えば上記のスーパーコンピュータ)という登場人物が存在していて, 検証者は証明者に何度も(多項式回の)質問をすることができます. 検証者はその質問に対する返答と自身の持つランダムネスを使って解があっていれば確率1で受理, そうでなければ確率$1/2$で拒否します. このような乱択検証が多項式時間でできるような判定問題のクラスをIP (interactive proof) といいます. 例えばクラスNPはNP証拠を出力する証明者を考えれば対話証明できるので, $\mathsf{NP}\subseteq \mathsf{IP}$です.

ところがクラスIPはNPとは違ってランダムネスを使える上に証明者に何度も質問することができます. これによってクラスIPはどこまで広くなるでしょうか? 驚くべきことに1990年に Sha92 LFKN92によってクラスIPはPSPACEと呼ばれるクラスと一致するという定理が示されました. PSPACEとは多項式ビットのメモリを用いて解ける判定問題のクラスで, NPよりもはるかに難しい(と予想されている)問題を含むとても広いクラスです. 要するにNP検証者に対話とランダムネスを付与すればその計算能力がものすごく向上することになります ($\mathsf{NP}\subseteq \mathsf{PSPACE}$は知られていますがこの包含関係が真かどうかは残念ながら未解決ですが...).

PCP定理とは, $\mathsf{IP}=\mathsf{PSPACE}$において, 左辺を$\mathsf{NP}$に置き換えたときに右辺がどうなるか?という疑問からスタートして研究されてきました. IPにおける証明者とは質問を表す文字列$x\in\{0,1\}^{\mathrm{poly}(n)}$を与えたときに$0$または$1$を返す関数$P\colon \{0,1\}^{\mathrm{poly}(n)}\to\{0,1\}$とみなすことができます(注1). ここで, この関数$P$をその真理値表(この文字列は$2^{\mathrm{poly}(n)}$ビットの文字列になる)と同一視したとき, 検証者は$P$という文字列に$\mathrm{poly}(n)$回アクセスして乱択を使って受理か拒否を判定することになります. これは, 長い証拠の高々$100$文字だけをみて乱択で出力を決定するPCP検証者と非常に似た設定を考えていることになります.

(注1) 証明者の返答が$\ell$ビットあるような対話証明において, $x$という質問を$(x,i)$という質問を「$x$に対する返答の$i$ビット目は何か?」という質問に置き換えれば返答を1ビットに制限したものに置き換えることができます.

なお, PCP定理はAroraらALMSS98によって証明されましたが, この証明は代数的な手法に基づく非常に複雑なものでした. 現在ではDinurDin07による比較的単純な証明が知られており, 本記事の証明も彼女の証明を紹介するというものになります. なお, この業績でDinurは2019年にゲーデル賞を受賞しています.

2. CSPとPCP

CSPのインスタンス$\mathcal{C}$と割り当て$\sigma\in\Sigma^n$に対して,
$$ \mathrm{UNSAT}(\mathcal{C},\sigma)=\Pr_{i\sim[m]}[P_i(x)=\mathrm{false}] $$
とし, $\mathrm{UNSAT}(\mathcal{C})=\min_{\sigma\in\Sigma^n}\mathrm{UNSAT}(\mathcal{C},\sigma)$とします. つまり$\mathrm{UNSAT}(\mathcal{C},\sigma)$は割当$\sigma$によって充足されない制約の割合を意味し, その中で最悪な割当を持ってきた時の割合を$\mathrm{UNSAT}(\mathcal{C})$とします. 明らかに,

$\mathcal{C}$が充足可能$\Rightarrow \mathrm{UNSAT}(\mathcal{C})=0$
$\mathcal{C}$が充足可能でない$\Rightarrow \mathrm{UNSAT}(\mathcal{C})\geq \frac{1}{m}$

が成り立ちます. 本記事で最終的に証明するのは次の定理です.

PCP定理の別の形

ある定数$c>0,k\in\mathbb{N}$, 多項式$p\colon\Nat\to\Nat$, 有限集合$\Sigma_0$と, 与えられた2-CSPのインスタンス$\mathcal{C}$を以下の性質を満たす別のk-CSPのインスタンス$\mathcal{C}'$に変換する多公式時間アルゴリズムが存在する: 任意の2-CSPインスタンス$\mathcal{C}$に対し,

$\mathrm{UNSAT}(\mathcal{C})=0 \Rightarrow \mathrm{UNSAT}(\mathcal{C}')=0$
$\mathrm{UNSAT}(\mathcal{C})>0 \Rightarrow \mathrm{UNSAT}(\mathcal{C}')\geq c$
$\mathcal{C}$の変数の個数を$n$とすると, $\mathcal{C}'$の変数の個数は高々$p(n)$.
$\mathcal{C}'$のアルファベットは$\Sigma_0$.

定理3を用いた定理1の導出

3彩色問題がNP完全であるという事実を証明なしで使います. この事実により, 3彩色問題に対してPCP検証者を構成すれば定理1が証明されます. PCP検証者$V$として以下のものを考えます. $\mathcal{C}$を入力とします.

定理3のアルゴリズムを用いて$\mathcal{C}$を変換して定理3の条件を満たす別の2-CSPインスタンス$\mathcal{C}'$を得る.
PCP検証者が受け取る証明$y$は$\mathcal{C}'$に対する割り当てとする.
$\mathcal{C}'$から一様ランダムに制約$P$を選び, $y$が$P$を充足するならば1, そうでなければ0を出力する.

この検証者はPCP検証者となります. 実際, $V$が見る文字数は高々$O(k\log_2|\Sigma_0|)$であり, これは入力サイズに依存しない定数です. 次にこれがPCPの条件を満たすことを確認します:

元のインスタンス$\mathcal{C}$が充足可能ならば, $\mathcal{C}'$も充足可能なので, $y$をその充足割り当てとすれば確率1で$V$は1を出力します.
元のインスタンス$\mathcal{C}$が充足可能でないならば, $\Pr[V\text{ outputs }0]=\mathrm{UNSAT}(\mathcal{C}')\geq c$です.

なお, PCPの定義では拒否確率が$1/2$となっていますが, これは上記のPCP検証者を$O(\log(1/c))$回動かして1度でも$0$を出力すれば$0$を出力するというようにすれば良いです.

定理3$\Rightarrow $定理1の議論では, CSPに関する定理3を使ってPCP検証者を構成しましたが, 逆にPCP検証者を使ってCSPのインスタンスを構成することができます. $q$クエリのPCP検証者を考えます. 実は厳密なPCP定理(定理1.2)よりPCP検証者は$r=O(\log n)$ビットのランダムビットを使うため, ありうる$2^{r}=n^{O(1)}$通りのランダムシードを全て列挙してそれぞれのランダムシードにおいてこのPCP検証者をシミュレートすると, それぞれは証明$y\in\{0,1\}^{\mathrm{poly}(n)}$のうち$q$文字だけをみて受理か拒否を決定します. ですので, $y\in\{0,1\}^{\mathrm{poly}(n)}$を変数とみなすと, $2^r$個の制約からなる$q$-CSPのインスタンスが構成できたことになります.

この$q$-CSPのインスタンスは, それが充足可能でないならば任意の割当$\sigma\in\{0,1\}^{\mathrm{poly}(n)}$に対して高々半分の制約しか満たされないという性質を持ちます.
このように見ると, あたかも純粋な計算量理論の結果に見える定理1,2は実はCSPという組合せ論っぽい側面を持っていることがわかります.

定理3のえらいところ

要するに定理3はCSPを別のCSPに変換できるということを主張していますが, 特に最後の条件「$\mathrm{UNSAT}(\mathcal{C})>0\Rightarrow \mathrm{UNSAT}(\mathcal{C}')\geq c$」という部分が難しいです. 一つでも充足されない$\mathcal{C}$の制約が存在すればその性質が$\mathcal{C}'$の多くの制約に伝播することを意味します. このように, 局所的な性質が大域的に伝播する (local-to-global)という性質が非自明なポイントであり, これはある種のエクスパンダー性とみなすことができます.