PCP定理 ～近似アルゴリズムの限界性定理～

0. 概要

　みなさんはPCP定理という単語を聞いたことがあるでしょうか？ PCP定理をうまく使うと, 様々な最適化問題に対して P $\neq$ NP の仮定のもとでの多項式時間アルゴリズムの近似率の限界を証明することが出来ます. このことから, PCP定理は計算複雑性理論においてとても重要な定理の一つと考えられています. 本記事では, PCP定理についてほんわかと説明します.

1. クラスNP

NPの定義を思い出しましょう.

定義1. 
言語 (判定問題) $L$ がNPに属する if ある決定的多項式時間アルゴリズム $V$ (検証者: Verifierと呼ぶ) と多項式$p:\mathbb{N}\to\mathbb{N}$ が存在して以下の2条件を満たす:
1. 任意のYesインスタンス $x\in L$ に対し, 文字列 $\pi \in\{0,1\}^{p(|x|)}$ (証明と呼ばれる) が存在して $V(x,\pi)=1$.
2. 任意のNoインスタンス$x\not\in L$と文字列 $\pi\in\{0,1\}^{p(|x|)}$ に対して $V(x,\pi)=0$.

例.
3SAT問題を考えてみましょう. 3SAT問題とは入力として論理式 $\varphi(x_1,\ldots,x_n)$ が 3CNF 形式で与えられ, 充足割当の存在性を判定するという問題です. $\varphi$ が 3CNF形式であるというのは,  $\varphi(x_1,\ldots,x_n) = C_1 \land \cdots \land C_m$ (ただし各 $C_i$ は $C_i = a\lor b \lor c$ の形で書ける式で節と呼ばれる) の形になっている論理式のことです.
$\varphi$ が充足可能である (i.e., Yesインスタンスである) とき, 「$\phi$は充足可能である」という主張は充足割当 $\pi$ をとってくることによって証明できます. 一方で充足不可能であるとき, 任意の割当 $\pi$ に対して $\varphi(\pi)=0$ となります. なので, 検証者 $V(\varphi, \pi)$ として $\varphi(\pi)$ を計算しその値をそのまま出力するアルゴリズムにすれば, 定義1の条件を満たすことが分かります.

2. クラスMA

クラスPCPの導入する前に, クラスMAを (ものすごく簡素に) 紹介します. ぶっちゃけPCPを理解する上では特に大事ではないので読み飛ばしてもらっても大丈夫です. クラスNPでは, Verifierは決定的アルゴリズムでしたが, これを多項式時間乱択アルゴリズムに置き換えて定義されるクラスをMA (Merlin Arthur)といいます. この記事では, 乱択アルゴリズムを $A(x,r)$ などと書き, $x$を入力, $r$を乱択アルゴリズム中で使うランダムビットとします. 例えば $\Pr_r[A(x,r)=1]$は, $A$が入力$x$に対して$1$を出力する確率と等しくなります. この表記では $A$は決定的アルゴリズムであることに注意してください ($r$ がランダムなとき, $A(x,r)$の挙動は乱択アルゴリズムのそれになります).

定義2.
言語 $L$ がMA に属する if ある決定的多項式時間アルゴリズム $A$ が存在して以下の2条件を満たす:
1. 任意のYesインスタンス $x\in L$ に対し, 文字列 $\pi\in\{0,1\}^{p(|x|)}$ が存在して $\Pr_r[A(x,\pi,r)=1]=1$.
2. 任意のNoインスタンス$x\not\in L$と文字列 $\pi\in\{0,1\}^{p(|x|)}$ に対して, $\Pr[A(x,\pi,r)=1]\leq 1/2$.

NPの定義 (定義1) と比較してみると, 雰囲気が掴みやすくなると思います. クラスMAについてもっとよく知りたい方はwikiなどをみてください. wikiやいろんな本を見ると, 条件1の部分は確率が1ではなく$\geq 2/3$などと書かれていることがありますが, 実は$1$にすることができます (例えばこのpdfを参照). なお, NP $\subseteq$ MA です. この包含関係が proper かどうかは未解決ですが,  計算量理論ではP=BPPであると信じられており, これが真だとするとNP=MAが成り立ちます (クラスBPPは多項式時間乱択アルゴリズムで解ける計算量のクラス).

3. クラスPCP

クラスMAでは, 検証者アルゴリズム$A$はインスタンス$x$, 証明$\pi$, ランダム文字列$r$を受け取る多項式時間アルゴリズムでした. PCPでは, 縛りプレイとして以下の制約を満たす多項式時間検証者アルゴリズム$A$を考えます. ($R,Q:\mathbb{N}\to\mathbb{N}$を函数とします):

a). $A$が使うランダム文字列 $r$ は $O(R)$ bit.
b). $A$は証明文字列 $\pi$ のうち, $O(Q)$ bit にしかアクセスできない.

それぞれの条件についてもう少しちゃんとみてみましょう. 条件aではランダム文字列$r$の長さを制限しています. 条件bでは, 検証者$A$は証明$\pi$は持っておらず, その代わりに $A$は「$\pi$の第$i$ビット目の値は何ですか？」というクエリに応答してくれるオラクルを持っていると仮定します (なので, NPやMAの検証者アルゴリズムとは設定が違います). 条件bは, $O(Q)$回しかクエリできないと言っています. これらの縛りプレイをしている検証者アルゴリズム$A$をPCP検証者 または PCP検証アルゴリズム (PCP verifier), 証明$\pi$をPCP証明 (PCP proof)と呼びます. 証明文字列$\pi$にアクセスするPCP検証者を $V^{\pi}$ と書きます. 特に, $V^{\pi}(x,r)$ は乱択アルゴリズムであることに注意してください.

図1. PCP検証者

＊この記事では, PCP検証アルゴリズムのクエリはnon-adaptive (非適応的) とします. つまり, $i$回目のクエリ内容はそれ以前のクエリの返答には依存しないものとします.

気持ちが分かりにくいと思うので, 以下に例を用意しました. とりあえず読めば雰囲気が掴めると信じています.

例 (SAT).
3SAT問題に対する自明な検証者は, 与えられた割当がインスタンスを充足するかどうかチェックするという簡単なものでした. これは, 長さ$n$の証明文字列$\pi$全てにアクセスする決定的アルゴリズムなので, PCP(0, $n$)検証者であると言えます.
別の例として, 以下の検証者$V^\pi$を考えてみましょう: $\phi$を3SATのインスタンス, $n,m$はそれぞれ$\phi$の変数と節の個数, $\pi\in\{0,1\}^n$は変数への割当とします. $V^{\pi}$はまず節 $C$ をランダムに一つ選択し, $C$に含まれる三つの変数について, $\pi$の割当をオラクルコールしてチェックし, その三変数の割当が$C$を充足するならば $V^{\pi}$は1を返し, そうでなければ 0 を返す (図2). この検証者アルゴリズムは, (a) $O(\log n)$ bitのランダム文字列を用い, (b) 3回のオラクルコールを行うので, PCP($\log n,1$)検証者であることがわかります. また, $\phi$がYesインスタンスならば$\Pr[V^\pi(\phi,r)=1]=1$ですし, Noインスタンスならば任意の割当$\pi$に対し$\Pr[V^\pi(\phi,r)=1] \leq 1-1/m$となります. つまり, Noインスタンスでもそれなりの確率で$1$を出力しかねないものとなっています. 乱択アルゴリズムでは独立な試行を繰り返すことにより成功確率を増幅するということが出来ますが, PCP検証者では試行を繰り返すとランダムビット長とクエリ回数が比例して増大してしまうので, このようなことは出来ません.

図2. 3SATのPCP検証アルゴリズムの例

ここで,  次の緩和した問題 (ギャップ問題と呼ばれる)を考えてみましょう:
1. 充足割当があるならばYesインスタンス;
2. 任意の割当に対し高々90%の節しか同時に充足できないならばNoインスタンス;
ここでは, 間のインスタンス, つまり91~99%の節が充足できるような論理式は絶対に入力として与えられないとします. すると, 上で考えた$V^\pi$は検証者としてうまく機能することが分かります. すなわち, Yesインスタンスならば$\Pr[V^\pi(\phi,r)=1]=1$ですし, Noインスタンスならば任意の割当$\pi$に対し$\Pr[V^\pi(\phi,r)=1] \leq 0.1$となるので, 少なくとも定義2の二つの条件は満たしていますよね. さて, このギャップ問題はMAXSATの0.91近似が出来れば解くことができます. MAXSATというのは同時に充足される節の個数を最大にするような割当を求めよという最適化問題で, 0.91近似アルゴリズムというのは, $0.91\times $最適値 $\leq$ 出力値 $\leq$ 最適値 の不等式を満たすアルゴリズムです. もし$\phi$がYesインスタンス(i.e., 充足可能) ならば, 最適値=1なので, 近似アルゴリズムの出力は0.91以上となります. 一方でNoインスタンス (i.e., 90%の節しか同時に充足できない) ならば, 出力値 $\leq$ 最適値 $\leq 0.9$となります. 間のインスタンスは絶対に来ないことが保証されるので, 入力の論理式に対して0.91近似アルゴリズムを走らせ, その出力値が0.91以上ならばYes, そうでないならばNo を出力すれば, ギャップ問題を解くことができますね. いよいよ近似アルゴリズムっぽい雰囲気が出てきました. まとめると, ギャップ問題にはPCP検証者が構築できることが分かります.


PCPのモチベーション.
元々PCP検証といった概念は, 「効率よく検証する」という研究の中で誕生しました. クエリ数に関して言えば, 例えばスーパーコンピュータに処理として判定問題を解かせる (例えばSATを解かせるとか) を投げたとき, スーパーコンピュータはYesかNoかを返すだけではなく, その証明 (例えば充足割当) をクライアントに送るべきですよね. でも証明の長さがすごく長い問題 (例えばNEXP: 非決定性TMで$2^{\mathrm{poly}(n)}$時間で解ける問題) とかスパコンに投げたとき, 証明自体もすごく長いので効率よく検証したくなります. そういったとき, クライアントはスパコンに対していくつかクエリを投げ, スパコンは持っている証拠を使ってクエリに回答するというプロトコルを考えることによって効率の良い検証が実現できます (ここでは, ランダムビット長の制限は考えていません).



定義3 (クラスPCP).
言語$L$ が クラス PCP($R,Q$) に属する if ある多項式時間PCP($R,Q$)検証者 $V$ が存在して以下の2条件を満たす:
1. 任意のYesインスタンス $x\in L$ に対し, 文字列 $\pi$ (PCP証明) が存在して, $\Pr[V^\pi(x,r)=1]=1$ ($|r|\leq O(R)$に注意).
2. 任意のNoインスタンス $x\not \in L$ に対し, 任意の文字列 $\pi$ に対して $\Pr[V^\pi(x,r)=1]\leq 1/3$.


例.
先ほどの3SATの例からわかることは
- 3SAT $\in$ PCP($n,0$).
- Gap3SAT $\in$ PCP($\log n,1)$.
でした.

自明な性質.

•  PCP($R,Q$) は ランダムビットを列挙することにより $2^{O(R)} \mathrm{poly}(n)$ 時間で解ける.
•  PCP($R,Q$) のPCP証明 $\pi$ の長さは $|\pi|\leq 2^{O(R)}Q$ としてよい. 実際, 各ランダムビット $r\in \{0,1\}^{O(R)}$ に対して PCP検証者は高々$Q$個の文字列しか見ないからである.
• 定義内にある確率1/3は, 任意の定数まで下げられる. 実際, PCP検証者アルゴリズムを定数回繰り返すだけで良い.

いよいよPCP定理について述べることができます. ステートメントは単純で, PCP定理は 3SAT $\in$ PCP($\log n,1$) を主張します. やばみが伝わるでしょうか.


定理1. (PCP定理).
NP = PCP($\log n,1$).

片方の包含関係 ($\supseteq$) は自明です. というのも, PCP検証アルゴリズムがあったら, $O(\log n)$ bit のランダム文字列を列挙出来るからです.

なお, 前述のNEXPに関しては次の結果が知られています:

定理2. (scaled-up PCP).
NEXP = PCP($\mathrm{poly}(n),1$).

4. 近似率の限界

PCP定理を使うといろんな最適化問題の近似率の限界が P$\neq$NPの仮定の下で成り立ちます. この部分について簡単に紹介します. キーワードは CSP (Constraint Satisfaction Problem) です.

NP=PCP($\log n,1$)なので, 3SATに対するPCP($\log n,1$)検証アルゴリズム $V$ が存在します. クエリ数を$q=O(1)$とおきます. 3SATのインスタンス $\phi$ とランダム文字列$r\in\{0,1\}^{O(\log n)}$ を固定すると, PCP検証者の出力 $V^{(\cdot)}(\phi,r)$は証明文字列$\pi$を$V^\pi(\phi,r)\in \{0,1\}$に写す写像と見なすことができます. さらにこの写像は, $\pi$の$q$箇所の値にのみ依存する (この性質を$q$-juntaと呼びます) ため, $V^{\pi}(\phi,r)=f(\pi[i_1],\ldots,\pi[i_q])$の形で書くができます ($i_1,\ldots,i_q$は$r$に依存するが, $f$は$r$に依存しない. また, non-adoptiveなものを考えているので, 例えば$i_4$は$\pi[i_1],\pi[i_2],\pi[i_3]$に依存しない).

そこで, 次の問題を考えます:

（＊）全ての$r\in\{0,1\}^{O(\log n)}$ に対して $f(\pi[i_1],\ldots,\pi[i_q])=1$となるような $\pi$ が存在するか？ 存在しないならば, 出来るだけ多くの$r$で $f(\pi[i_1],\ldots,\pi[i_q])=1$ となるような $\pi$を探せ.

この問題の前半部分は3SATっぽい形をしていることが分かります. 実際, $\bigwedge_{r} f(\pi[i_1],\ldots,\pi[i_q])$ の形で書くことができますよね. また, PCP証明の長さは高々$2^{O(\log n)}\cdot O(1)=n^{O(1)}$ とできます. つまり, PCP証明文字列 $\pi$ を変数とみなし, 3SATっぽい問題（＊）を考えるという点がミソです (図2). この問題（＊）は専門用語で$q$CSPと呼びます. $q=3$のとき, $3$CSPは3SATを含むので, NP-hardです. PCP定理を使ってqCSPの近似困難性を示していくことになります. また, 後半部分はGap問題ぽくなります. このことをちゃんとみてみましょう.

• $\phi$がYesインスタンスの場合, あるPCP証明 $\pi$ が存在し, $\Pr[V^\pi(\phi,r)=1]=1$となります. 言い換えると, 問題（＊）は充足可能であることが分かります.
• $\phi$がNoインスタンスの場合, 任意のPCP証明 $\pi$ に対し, $\Pr[V^\pi(\phi,r)=1]\leq 1/3$となります. 言い換えると, 問題（＊）は高々33%の$r$に対してしか充足できません.

図3. 問題（＊）のインスタンスを構成するの図

今, 最大化問題（＊）に対する多項式時間$2.99$-近似アルゴリズムが存在するとします. すると, 3SATを多項式時間アルゴリズムが構成できます. というのも, 3SATのインスタンス$\phi$, 3SATのPCP検証者$V$を使って問題（＊）のインスタンスを構成します. このインスタンスに対して近似アルゴリズムを適用すると,  $\phi$ が充足可能かどうかが区別できます ($\phi$がYesインスタンスの場合は必ず近似アルゴリズムの出力値 $>1/2.99 > 1/3$  となる一方で, Noインスタンスの場合は出力値が $\leq 1/3$ となる).

4.1. 3-SATの近似率限界

問題（＊）を3SATに普通に変形すると, 実は近似率は定数倍くらいしか変わりません. すなわち, P$\neq$NPの下では3SATに対するPTASが存在しないことが帰結されます. この方法では近似率限界は凄く悪い ($1-10^{-6}$-近似はできないくらいしか言えない. $1-10^{-6}$は定数) のですが,  Håstad's 3bit PCP theorem という結果によって, 以下の結果が示せます.

定理 (Håstad)

P$\neq$NP の仮定の下では, 任意の定数$\epsilon>0$に対して MAX3SAT に対する多項式時間$(7/8+\epsilon)$-近似アルゴリズムは存在しない.

一方, 3SATに対する多項式時間$7/8$-近似アルゴリズムが存在するので, 上の限界はtightです.

最大クリークから3SATへの普通の帰着 (NP-hardnessを示すときに使うやつ) を考えると, 実はこの帰着は近似率を保存するので, 最大クリークに対する近似不可能性も示すことができます. さらに, グラフの適当なプロダクトを取ることで近似率を増幅させることができ, 「任意の定数$\epsilon>0$に対して最大クリークは多項式時間で$n^{1-\epsilon}$-近似できない」ことがP$\neq$NPの下でいうことができます.