ロバストPCPとPCP of Proximity

ロバストPCPとPCP of Proximity

PCP定理の証明を構成する二つの重要な要素ロバストPCPとPCP of Proximity (PCPP)について説明します. これらの概念を用いたPCP定理の証明の枠組みはBen-Sassonら[1]によって導入されましたが独立にDinurとReingold[2]のassignment testerと呼ばれる枠組みとほぼ同じです. どれも, 当時知られていた非常に複雑なPCP定理の証明[3]を整理して理解しようとする中で誕生した概念であり, 後にDinur[4]によってエクスパンダーグラフ上のランダムウォークに基づく非常に簡単な証明が与えられました. 彼女はこの業績で2019年にゲーデル賞を受賞しています.

1. 定義の準備

有限長の文字列の集合$L\subseteq \{0,1\}^*$を言語といいます. 計算量理論では, 言語を判定問題(与えられた$x\in\{0,1\}^*$に対して$x\in L$かどうか判定せよという問題)と同一視します. 

同じ長さの二つの文字列$x,y\in\{0,1\}^n$に対してその距離を正規化されたハミング距離で定めます. すなわち$\mathrm{dist}(x,y)=\frac{1}{n}\sum_{i=1}^n \mathbf{1}_{x(i)\neq y(i)}$とします. 文字列の集合$\mathcal{C}\subseteq \{0,1\}^n$と$x\in\{0,1\}^n$に対して$\mathrm{dist}(x,\mathcal{C})=\min_{y\in\mathcal{C}}\mathrm{dist}(x,y)$とします. 特に$\mathcal{C}=\emptyset$のときは$\mathrm{dist}(x,\mathcal{C})=1$と定義します. 関数$D\colon\{0,1\}^n\to\{0,1\}$に対して$D^{-1}(1)=\{x\in\{0,1\}^n\colon D(x)=1\}$とします.

言語$L$に対する検証者とはオラクルアルゴリズム$V^\pi(x)$であってオラクル$\pi$の助けを借りながら$x\in L$かどうかを判定するものを指します. その際, オラクル$\pi\in\{0,1\}^*$は$x\in L$を主張する証明として機能する文字列であり, インデックス$i$に対して$\pi(i)\in\{0,1\}$を返すオラクルとして解釈します. たとえば$L$が充足可能な論理式の全体であるならば, $x$が表す論理式の充足可能性を判断するために例えば$\pi$として$x$の充足割当を持ってくれば証明として機能します. 検証者の能力によって様々なシチュエーションが考えられます.

NP検証者は決定的な多項式時間検証者$V^\pi(x)$であって以下を満たすものです:

1. $x\in L$ならばあるオラクル$\pi$が存在して$V^\pi(x)=1$.
2. $x\not\in L$ならば任意のオラクル$\pi$に対して$V^\pi(x)=0$.

条件1を満たすオラクル$\pi$を本記事ではNP証明と呼ぶことにします. また, NP検証者を持つ言語の集合を$\mathsf{NP}$と表します. 有名な$\mathsf{P}\neq\mathsf{NP}$問題は任意の$L\in \mathsf{NP}$が決定的多項式時間で解けるかどうかを問うています.

PCP検証者は乱択な検証者$V^\pi(x)$であって以下を満たすものです:

1. 任意の$x\in L$に対してあるオラクル$\pi$が存在して$\Pr[V^\pi(x)=1]=1$.
2. ある定数$s>0$が存在して, 任意の$x\not\in L$と任意のオラクル$\pi$に対して$\Pr[V^\pi(x)=0]\geq s$.
3. 任意の$n\in\mathbb{N}$, $x\in\{0,1\}^n$に対して$V^\pi(x)$は高々$q(n)$回のオラクルアクセスを行い, 高々$r(n)$ビットのランダムビットを使う.

条件3の$r(n)$をランダムネス複雑度, $q(n)$を$V$のクエリ複雑度と呼ぶことにします. このような検証者を持つような言語の集合を$\mathsf{PCP}(r,q)$と定義します. 条件1のオラクル$\pi$をPCP証明と呼ぶことにします(*1).

(*1). PCPとはProbabilistic Checkable Proof (確率的検証可能な証明)の略なので, PCP証明という言葉は「証明」の部分が二重になり気持ち悪く本来はPC証明と呼ぶべきですが, そう呼んでしまうとあとでPCPPという用語も出てきてややこしくなるのであえてPCP証明と呼ぶことにします.

PCP定理は$\mathsf{NP}=\mathsf{PCP}(O(\log n),O(1))$を主張する定理です.

2. PCP検証者と制約充足問題

制約充足問題(CSP; Constraint Satisfaction Problem)とは大雑把にいうと「連立方程式の解を見つけよ」という問題です. $n$を変数の個数とし, $[n]=\{1,\dots,n\}$上の集合族$\mathcal{S}$ (つまり各$S\in\mathcal{S}$は$S\subseteq [n]$) とそれで添字づけられた関数族$(D_S)_{S\in\mathcal{S}}$を考えます. ここで各$D_S\colon \Sigma^S\to\{0,1\}$とし, $\Sigma$は有限集合とします (アルファベットと呼びます). 制約充足問題とは

ある$x\in\Sigma^{[n]}$が存在して全ての$S\in\mathcal{S}$に対し$D_S(x|_S)=1$となるか?

を判定する問題です. ここで$x|_S\in\Sigma^S$は$x$の$S$への制限です. 

特に$\Sigma=\{0,1\}$のときのCSPを二値CSP(binary CSP), 全ての$S\in\mathcal{S}$に対して$|S|\leq q$を満たすCSPを$q$-CSPと呼びます. 本記事では特に断りのない限り二値の$q$-CSPを考えます.

PCP検証者$V^\pi(x)$はある集合$S$に対して$\pi|_S$を見て出力を決めるので, インデックス集合$S$(ただし$|S|\leq q$)と関数$D\colon \{0,1\}^n\to \{0,1\}$をランダムに生成し, $D(\pi|_{S})$を出力するアルゴリズムと捉えることができます ($\mathcal{S}$や$D$は入力$x$に依存). これを, $\mathcal{S}$から適当な分布に従ってランダムに選んだ$S$に対して$D_S(\pi|_S)$を出力すると捉えれば, PCP検証者は二値$q$-CSPのインスタンス$(D_S)_{S\in\mathcal{S}}$と同一視することができます. このCSPの変数は$\pi$です. 簡単のため$S$の分布を一様分布とします(*2). このとき, PCP検証者の条件は以下のように書き換えられます:

1. 任意の$x\in L$に対してある$\pi$が存在して全ての$S\in\mathcal{S}$に対して$D_S(\pi|_S)=1$.
2. 任意の$x\not\in L$と任意の$\pi$に対して$\Pr_S[D_S(\pi|_S)=0]\geq s$. すなわち, $D_S(\cdot)$が充足されないような$S$が$s\cdot |\mathcal{S}|$個ある.
3. $|\mathcal{S}|=2^r$かつ$|S|\leq q$である (つまり$\mathcal{S}$上一様ランダムに選ぶときに長さ$r$のランダムビットを使う).

このように捉えるとMAX-SAT(最も多くの節を充足する割当を見つける問題)の近似アルゴリズムの存在性とPCP定理が関係することがわかりやすくなるでしょう.

(*2). $\mathcal{S}$が多重集合であることを許容すれば$S\sim\mathcal{S}$を一様分布とすることができます. 実際, ある集合$S\in\mathcal{S}$が選ばれやすいのであれば, その分だけ$S$を$\mathcal{S}$に追加することで一様分布によってシミュレートすることができます.

3. PCP検証者のロバスト性

条件2の代わりに以下の条件2'を満たすPCP検証者をロバストなPCP検証者といいます:

• (条件2') ある定数$s_1,s_2>0$が存在して任意の$x\not\in L$に対して$\Pr_S[\mathrm{dist}(\pi|_S,D_S^{-1}(1))\geq s_1]\geq s_2$.

条件2'はPCP検証者の条件2よりも強いことを要請しています. 実際, 検証者が条件2'を満たすならば$\Pr[V^{\pi}(x)=0]=\Pr_S[\pi|_S\not\in D^{-1}(1)]\geq \Pr_S[\mathrm{dist}(\pi|_S,D^{-1}(1))\geq s_1]\geq s_2$となるからです.

PCP定理の証明はあるNP完全問題$L$に対してクエリ複雑度の大きいロバストなPCP検証者を構成し, これをPCP of Proximityと組み合わせてクエリ複雑度を下げることによって所望のPCP検証者を得るという流れになります.

4. PCP of Proximity (PCPP)

PCPP検証者とは, 関数$D$(を記述する回路), $D$の割当$x$, 証明$\pi$が与えられたときに$D(x)=1$かどうかを検証する乱択アルゴリズムです. ただし, $x$と$\pi$が両方ともオラクルで与えられ, オラクルへのクエリアクセスの回数が制限されます(*3).

PCPP検証者とは乱択オラクルアルゴリズム$V^{x,\pi}(D)$であって以下を満たすものです:

1. $D(x)=1$ならば, ある$\pi$が存在して$\Pr[V^{x,\pi}(D)=1]=1$.
2. $\mathrm{dist}(x,D^{-1}(1))\geq c_1$ならば$\Pr[V^{x,\pi}(D)=0]\geq c_2$.
3. 任意の$n\in\mathbb{N}$, $x\in\{0,1\}^n,D$に対して$V^{x,\pi}(D)$は高々$q(n)$回のオラクルアクセスを行い, 高々$r(n)$ビットのランダムビットを使う.

直感的にはPCPP検証者とは充足割当からの近さ(proximity)を判定する検証者です. 条件1を満たすオラクル$\pi$をPCPP証明と, $x$を証明と呼ぶことにします. 条件2において$D^{-1}(1)=\emptyset$(つまり$D$が充足不可能)のときは常に$\mathrm{dist}(x,D^{-1}(1))\geq c_1$が成り立つことに注意してください.

(*3). 実際にはペア言語$L\subseteq \{0,1\}^*\times\{0,1\}^*$を考え, $(x,y)\in L$かどうかの検証者として定義されます. この例ではペア言語$L$として$(D,x)\in L\iff D(x)=1$と定義します.

命題. PCPP検証者が存在するならばSATに(同じ$r,q,s$の)PCP検証者が存在する.

証明. SATに対するPCP検証者を構成すればよい. 入力の論理式$C\colon\{0,1\}\to\{0,1\}$に対し, その充足割当$x$を証明としてPCPP検証者$V^{x,\pi}(C)$をシミュレートすれば良い. 実際, $C$が充足可能ならばその充足割当$x$を証明すればよく, 充足可能でないならば$D^{-1}(1)=\emptyset$となり, PCPPの条件2より健全性も成り立つ.

5. ロバストなPCP検証者とPCPP検証者の合成

NP完全な言語$L$に対してロバストなPCP検証者$V_0$であってクエリ複雑度が$Q(n)\gg 1$, ランダムネス複雑度$R$なるものが存在するとします. さらに, クエリ複雑度$q$, ランダムネス複雑度$r$のPCPP検証者の存在性を仮定します (ここでそれぞれの条件2に出てくる定数について$c_1=s_1$を仮定します).

• 2節で説明したように$V_0$をCSPのインスタンス$(D_S)_{S\in\mathcal{S}}$と同一視します. ただし各$|S|=Q$です. $V_0$を走らせたときに得られるランダムな$S\sim\mathcal{S}$に対して関数$D_S$を考えます.
• ペア言語$(D_S,\pi|_S)$に対してPCPP検証者を走らせます. ここで$\pi|_S$は証明として扱います.

こうすると, 全体のクエリ複雑度は$q$, ランダムネス複雑度は$R+r$のPCP検証者を得ることができます. ちゃんとPCP検証者になっているか確認してみましょう.

• $x\in L$ならば全ての$S\in\mathcal{S}$に対して$D_S(\pi|_S)=1$となるため, PCPP検証者も必ず$1$を出力します.
• $x\not\in L$ならば, ロバスト性より確率$s_2$で$\Pr_{S\sim\mathcal{S}}[D_S(\pi|_S)=0]\geq s_1$となります. この事象で条件づけたとき, $c_1=s_1$の仮定より, 確率$c_2$でPCPP検証者は$0$を出力します. すなわち確率$s_2c_2$で上記の検証者は$0$を出力します.

以上の議論より, $R+r=O(\log n)$, $q=O(1)$を満たすように作ればPCP定理が証明できたことになります.

6. まとめ

PCP検証者を構成するために, まず「充足割当からの近さ」を増加させるロバストPCP検証者と「充足割当からの近さ」を検証するPCPP検証者という概念を用いました. 距離に着目するアイデアは誤り訂正符号に基づいたものです.

参考文献

[1] E. Ben‐Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan. “Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.” SIAM Journal on Computing 36 (4): 889–974. https://doi.org/10.1137/S0097539705446810. (2006).

[2] I. Dinur, and O. Reingold. “Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem.” SIAM Journal on Computing 36 (4): 975–1024. https://doi.org/10.1137/S0097539705446962. (2006).

[3] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. “Proof Verification and the Hardness of Approximation Problems.” Journal of the ACM 45 (3): 501–55. https://doi.org/10.1145/278298.278306. (1998).

[4] I. Dinur, “The PCP Theorem by Gap Amplification.” Journal of the ACM 54 (3): 12 – es. https://doi.org/10.1145/1236457.1236459. (2007).