ラベル被覆(label cover)とは、2 部グラフの各頂点にラベルを付け、辺ごとに許されたラベルの組の関係を満たす辺の割合を最大にする問題(最小化の版もある)である。辺を一様に選んで端点を 2 人に問う 2 人 1 回のゲームとみると、満たす辺の割合の最大値はゲームの値に等しく、E3CNF から作る例では満たせる辺の最大数が $2m+k^*$ になって定数のギャップの NP困難性が従う。並列反復定理で反復すると、どの定数 $\delta>0$ についても、すべての辺を満たせる例と割合 $\delta$ 以下しか満たせない例の区別が NP困難になる。この問題は集合被覆問題への還元など多くの近似の困難さの証明の出発点で、関係を全単射に限ると Unique Games の問題になる。
ラベル被覆(label cover)は、2 部グラフの各頂点にラベルを 1 つずつ付け、辺ごとに許されたラベルの組の関係を満たす辺の割合をできるだけ大きくする問題である(最小化の版もある)。2 部グラフの片側を一方の参加者、もう片側を他方の参加者への問いとみると、ラベル付けは 2 人 1 回のゲームの戦略で、満たす辺の割合はゲームの勝率である。
PCP定理 と 並列反復定理 を合わせると、どの定数 $\delta>0$ についても、すべての辺を満たせる例と割合 $\delta$ 以下しか満たせない例の区別が NP困難になる(cor-lc-amplify)。この「完全性 $1$ と任意に小さな健全性」のギャップをもつ問題から出発して、集合被覆などの多くの問題の近似の困難さが導かれる(WS11 §16.4、p. 425)。辺の関係を全単射に限った特別な場合は Unique Games予想 の問題で、そこでは完全性 $1$ の区別は易しくなる。
この記事では、3SAT からの還元(prop-lc-e3sat)と、ギャップの増幅(cor-lc-amplify)、集合被覆への還元の核となる補題(lem-lc-decode)を証明する。一般の制約言語の計算量の分類は 制約充足問題 で、PCP の定義とギャップ問題の一般論は PCP定理 で扱う。
ラベル被覆の例 $I$ とは、2 部グラフ $(V_1,V_2,E)$($E\subset V_1\times V_2$、$E\ne\emptyset$)、有限集合 $L_1,L_2$(ラベル の集合)、各辺 $(u,v)\in E$ に与えた空でない関係 $R_{uv}\subset L_1\times L_2$ の組である。
$V_1$ のどの頂点の次数も $d_1$、$V_2$ のどの頂点の次数も $d_2$ であるとき $I$ を $(d_1,d_2)$ 正則、$d_1=d_2=d$ のとき $d$ 正則 という。$d$ 正則なら $|V_1|=|V_2|=|E|/d$ である。
各辺 $(u,v)$ と各 $\ell_2\in L_2$ について、$(\ell_1,\ell_2)\in R_{uv}$ となる $\ell_1$ が高々 1 つであるとき、$I$ は 射影の性質 をもつという。$V_2$ の側のラベルが、辺ごとに $V_1$ の側のラベルを(あれば)決める。$L_1=L_2$ で、各 $R_{uv}$ が全単射のグラフであるものが Unique Games の例である(WS11 p. 425、Unique Games予想 の定義「Unique Games の例と値」)。
ゲームとしての見方. 辺を一様に選び、端点 $u$ を Alice に、$v$ を Bob に問い、答えのラベルの組が $R_{uv}$ に入れば勝つゲームを $G_I$ とする。$G_I$ の戦略は $\sigma_1,\sigma_2$ の組そのもので、勝率は満たす辺の割合なので、$\mathrm{val}(G_I)=\mathrm{val}(I)$ である(並列反復定理 の定義「ゲームと値」の値。Rao08 p. 2)。
各節がちょうど 3 個の相異なる変数のリテラルからなる CNF を E3CNF という。
変数 $x_1,\dots,x_n$、節 $C_1,\dots,C_m$ の E3CNF $\varphi$ から、次の例 $I(\varphi)$ を作る。$V_1=\{x_1,\dots,x_n\}$、$V_2=\{C_1,\dots,C_m\}$、$x_i$ が $C_j$ に現れるとき辺 $(x_i,C_j)$ を置く。$L_1=\{0,1\}$、$L_2=\{0,1\}^3$ とし、$C_j$ の 3 変数を $x_p,x_q,x_r$($p< q< r$)として、$R_{x_iC_j}$ は、$(b_p,b_q,b_r)$ が $C_j$ を充足し $b=b_i$ となる組 $(b,(b_p,b_q,b_r))$ の全体とする。このとき
1:$C_j$ のラベル $(b_p,b_q,b_r)$ と辺 $(x_i,C_j)$ について、許される $x_i$ のラベルは $b_i$ だけで、組が $C_j$ を充足しなければ 1 つもない。
2:辺は $3m$ 本で、各 $C_j$ に 3 本ずつある。割り当て $s\in\{0,1\}^n$ が $k$ 個の節を充足するとき、$\sigma_1(x_i)=s_i$ とし、充足される $C_j$ には $s$ の 3 変数の値を、充足されない $C_j$ には 1 変数だけ値を反転して $C_j$ を充足する組を付ける(E3CNF の節の 3 つのリテラルは相異なる変数なので、どのリテラルを真にしても節は充足される)。前者では 3 本、後者では反転しなかった 2 本の辺が満たされるので、合計 $3k+2(m-k)=2m+k$ 本である。
逆に、ラベル付け $(\sigma_1,\sigma_2)$ をとり、$s_i:=\sigma_1(x_i)$ が充足する節の数を $k$ とする。$C_j$ で満たされる辺の数は、$\sigma_2(C_j)$ が $C_j$ を充足しなければ $0$、充足すれば $s$ と値が一致する変数の数である。$s$ が $C_j$ を充足するなら高々 3 本である。充足しないなら、$C_j$ を充足する組は $s$ とどこか 1 変数で異なるので、高々 2 本である。合計は $3k+2(m-k)=2m+k\le2m+k^*$ である。$\square$
任意の $\varepsilon>0$ について、ラベル被覆の例で $\mathrm{val}(I)=1$ のものと $\mathrm{val}(I)\le\frac{23}{24}+\varepsilon$ のものとの区別は NP困難である(WS11 Theorem 16.25、p. 426)。
任意の $\eta>0$ について、E3CNF で全部の節が充足できるものと、充足できる節の割合が $\frac78+\eta$ 以下のものとの区別は NP困難である(Håstad。WS11 Theorem 16.23、p. 424。PCP定理 の定理「Håstad の定理」)。$\varphi$ を $I(\varphi)$ に移すと、prop-lc-e3sat の 2 により前者は $\mathrm{val}=1$、後者は $\mathrm{val}\le(2+\frac78+\eta)/3=\frac{23}{24}+\frac\eta3$ になる。$\eta=3\varepsilon$ とすればよい。$\square$
各変数がちょうど 5 個の節に現れる E3CNF に限っても同様の定数のギャップが NP困難で、上の還元から $(5,3)$ 正則な例が得られる(WS11 Theorem 16.26、p. 427。この記事では証明しない)。$(d_1,d_2)$ 正則な例 $I$ から、$V_1'=V_1\times V_2$、$V_2'=V_2\times V_1$ とし、$(u,v)$ と $(v',u')$ を $(u,v'),(u',v)\in E$ のとき結び、関係は $R_{uv'}$ とする例を作ると、$d_1d_2$ 正則で値が変わらず、射影の性質も保たれる(同 p. 427、Theorem 16.27)。辺は $(u',v)$ を固定すると $I$ の写しに分かれるからである。
例 $I$ と $k\ge1$ について、$V_1^k,V_2^k$ を頂点、$E^k$ の元 $((u_1,\dots,u_k),(v_1,\dots,v_k))$ を辺、$L_1^k,L_2^k$ をラベルとし、ラベルの組が座標ごとに $R_{u_iv_i}$ に入ることを関係とする例を $I^{\otimes k}$ と書く(WS11 pp. 427–428)。射影の性質と $d$ 正則性($d^k$ 正則になる)は保たれる。
任意の $\delta>0$ について、射影の性質をもつ $d$ 正則なラベル被覆の例($d$ とラベルの数は $\delta$ だけで決まる定数)で $\mathrm{val}=1$ のものと $\mathrm{val}\le\delta$ のものとの区別は NP困難である。とくに P $\ne$ NP なら、どの定数 $\alpha>0$ についても、最大化の版の $\alpha$ 近似の多項式時間算法はない(WS11 Corollary 16.30、p. 428)。
$I^{\otimes k}$ の辺の一様分布は $G_I$ の問いの分布の $k$ 個の独立な積であり、ラベル付けは $G_I^k$ の戦略と同じものなので、$\mathrm{val}(I^{\otimes k})=\mathrm{val}(G_I^k)$ である(どの辺にも現れない頂点のラベルは値に効かない)。
cor-lc-constant と正則な例への変形(上の折りたたみ)により、射影の性質をもつ $15$ 正則な例で、$\mathrm{val}=1$ と $\mathrm{val}\le1-\varepsilon_0$($\varepsilon_0>0$ は定数)の区別は NP困難である。この例のラベルの数は $|L_1||L_2|=16$ である。並列反復定理 の系「必要な反復の回数」により、$k$ を $\varepsilon_0,\delta$ だけで決まる定数にとれば、$\mathrm{val}(I)\le1-\varepsilon_0$ のとき $\mathrm{val}(I^{\otimes k})=\mathrm{val}(G_I^k)\le\delta$ である。$\mathrm{val}(I)=1$ なら、満たすラベル付けを座標ごとに並べて $\mathrm{val}(I^{\otimes k})=1$ である。$k$ は定数なので $I^{\otimes k}$ の大きさは $I$ の大きさの多項式で、多項式時間で書き出せる。
後半:$\alpha$ 近似の算法 $\mathcal A$ があれば $\delta< \alpha$ として、$\mathrm{val}=1$ の例では $\mathcal A$ は割合 $\alpha>\delta$ 以上の辺を満たすラベル付けを返し、$\mathrm{val}\le\delta$ の例ではそうならないので、2 つを区別できる。$\square$
$k$ を入力の大きさとともに $\log$ の冪で増やすと、健全性は $2^{-\log^{1-\epsilon}|E|}$ まで下がるが、還元の時間は準多項式になり、結論は「NP が準多項式時間で解けないなら」という仮定のもとでのものになる(WS11 Theorem 16.31、p. 429)。
$U$ を有限集合とし、$U$ の部分集合の族から和集合が $U$ になる部分族をできるだけ少なく選ぶ問題を(重みなしの)集合被覆問題 という。
$h,t$ を正の整数とする。集合 $U=\{1,\dots,s\}$ と $U$ の部分集合 $A_1,\dots,A_t$ の組が パラメータ $h$ の分割系 であるとは、$\bar A_i:=U\setminus A_i$ として、相異なる $h$ 個の添字 $i_1,\dots,i_h$ をどう選び、各 $i_j$ について $B_{i_j}\in\{A_{i_j},\bar A_{i_j}\}$ をどう選んでも $B_{i_1}\cup\cdots\cup B_{i_h}\ne U$ となることをいう(WS11 p. 429)。
$t\ge h$ のとき、$h$ 個より少ない添字で選んだ和集合も、添字を足して $h$ 個にした和集合に含まれるので $U$ にならない。$s=2^{2h+2}t^2$ の分割系を作る決定的な算法もある(WS11 p. 431)。
各 $A_i$ を $2^U$ から一様に独立に選ぶ。添字 $h$ 個と $A,\bar A$ の選び方を固定すると、各点 $x\in U$ が選んだ各集合に入らない確率は $1/2$ で、これらは独立なので、$x$ が和集合に入らない確率は $2^{-h}$、和集合が $U$ になる確率は $(1-2^{-h})^s\le e^{-s/2^h}$ である。選び方は $\binom th2^h\le(2t)^h$ 通りなので、分割系にならない確率は $(2t)^he^{-s/2^h}$ 以下である。$s=2^hh\ln(4t)$ ならこれは $2^{-h}$ 以下である(WS11 Lemma 16.35、p. 431)。
1:すべての辺を満たすラベル付け $(\sigma_1,\sigma_2)$ について $S_{u,\sigma_1(u)}$、$S_{v,\sigma_2(v)}$ を選ぶ。辺 $(u,v)$ で $i=\sigma_1(u)$、$j=\sigma_2(v)$ とすると $(i,j)\in R_{uv}$ なので、$\{(u,v)\}\times U=\{(u,v)\}\times(A_i\cup\bar A_i)\subset S_{u,i}\cup S_{v,j}$ である。
2:頂点 $w$ について、被覆に入る $S_{w,\cdot}$ の個数を $n_w$ とし、$n_w\ge h/2$ の頂点を 重い という。集合の総数から、重い頂点は $\frac14(|V_1|+|V_2|)$ 個以下である。$d$ 正則なので、重い頂点に接する辺は $d\cdot\frac14(|V_1|+|V_2|)=\frac12|E|$ 本以下で、両端が重くない辺の集合 $E_0$ は $|E_0|\ge\frac12|E|$ を満たす。
$(u,v)\in E_0$ とする。台集合の $\{(u,v)\}\times U$ の部分に効くのは $S_{u,i}$($A_i$ の写し)と $S_{v,j}$($\bar A_{i(j)}$ の写し。$i(j)$ は $(i(j),j)\in R_{uv}$ となる唯一の $i$)だけで、その個数は $n_u+n_v< h$ である。被覆に入る $S_{u,i}$ の $i$ と $S_{v,j}$ の $i(j)$ が一致する組がなければ、これらは相異なる $h$ 個未満の添字から $A$ か $\bar A$ の一方ずつを選んだものになり、分割系の性質から $\{(u,v)\}\times U$ を覆わない。よって、被覆に入る $S_{u,i}$、$S_{v,j}$ で $(i,j)\in R_{uv}$ となるものがある。
各頂点 $w$ で、被覆に入る $S_{w,\cdot}$ の添字から一様にランダムに 1 つ選んでラベルとする(被覆に入るものがなければ任意に選ぶ)。$(u,v)\in E_0$ は確率 $1/(n_un_v)>4/h^2$ 以上で満たされるので、満たされる辺の数の期待値は $\frac4{h^2}|E_0|\ge\frac2{h^2}|E|$ 以上である。条件付き期待値の方法で、頂点を 1 つずつ、期待値を下げないラベルに固定していけば、決定的に得られる。$\square$
$h=\log_2(|E||L_1|)$ とし、健全性が $1/\log_2^2(|L_1||E|)$ まで下がった例(cor-lc-amplify の後の準多項式の還元で $k=O(\log\log n)$ にとったもの。WS11 Lemma 16.33、p. 429)にこの還元を当てる。$h/8$ 倍以内の近似算法があれば、$\mathrm{val}=1$ の例では $\frac h8(|V_1|+|V_2|)$ 個以下の被覆が得られ、lem-lc-decode により割合 $2/h^2>1/h^2$ の辺を満たすラベル付けが得られる。健全性の側ではそのようなラベル付けはないので、2 つの場合を区別できる。分割系の大きさを多項式に保つと $h$ は台集合の大きさ $N$ の $\log$ の定数倍以上になり(パラメータの計算は WS11 p. 431)、NP の問題がすべて $n^{O(\log\log n)}$ 時間で解けるのでない限り、重みなしの集合被覆問題に $\frac1{32}\log_2N$ 倍の近似の多項式時間算法はない(WS11 Theorem 16.32、pp. 429–431)。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| cor-lc-amplify で、関係が全単射に限られないこと(全単射のものに狭める) | Unique Games の例 | 値 $1$ の例との区別が NP困難であること(P $\ne$ NP のもと) |
| lem-lc-decode の 1 で $\mathrm{val}(I)=1$ であること | $V_1=\{u_1,u_2\}$、$V_2=\{v_1,v_2\}$ の完全 2 部グラフで $L_1=\{1,2\}$、$L_2=\{1\}$、$R_{uv_1}=\{(1,1)\}$、$R_{uv_2}=\{(2,1)\}$($u\in V_1$、$h\ge2$) | $\lvert V_1\rvert+\lvert V_2\rvert$ 個の集合で被覆できること |
| prop-lc-e3sat で、各節がちょうど 3 個の相異なる変数をもつこと | 1 つの節 $x_1\vee x_2$ | 満たせる辺の最大数が $2m+k^*$ であること |
1 行目:関係が全単射なら、すべての辺を満たせるかは、連結成分ごとに 1 頂点のラベルを全部試して伝播させれば多項式時間で分かる(Unique Games予想 の命題「すべての辺を満たせるかは多項式時間で分かる」)。よって P $\ne$ NP なら、値 $1$ の例と値 $\delta$ 以下の例の区別は NP困難でない。
2 行目:$I$ は射影の性質をもつ $2$ 正則な例で、$u\in V_1$ のラベルが $i$ なら満たす辺は $(u,v_i)$ だけなので $\mathrm{val}(I)=\frac12$ である。$\{(u,v_1)\}\times U$ に効く集合は $S_{u,1},S_{u,2},S_{v_1,1}$($A_1,A_2,\bar A_1$ の写し)だけで、$h\ge2$ と分割系の性質から $A_1\cup A_2\ne U$、$A_2\cup\bar A_1\ne U$ なので、被覆には $S_{u,1}$ と $S_{v_1,1}$ が要る。同様に辺 $(u,v_2)$ から $S_{u,2}$ と $S_{v_2,1}$ が要るので、被覆には $2\cdot2+2=6>4=\lvert V_1\rvert+\lvert V_2\rvert$ 個の集合が要る。
3 行目:同じ構成でラベルを $\{0,1\}^2$ にとると、辺は $(x_1,C_1),(x_2,C_1)$ の 2 本で、$m=1$、$k^*=1$ だから $2m+k^*=3$ となり、辺の本数 $2$ を超える。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する