Unique Games予想(unique games conjecture)とは、各辺 $uv$ に $[k]$ の全単射 $\pi_e$ を付けたグラフの頂点に $[k]$ の値 $L$ を付けて $\pi_e(L(u))=L(v)$ となる辺の割合を最大にする問題について、どの $\varepsilon,\delta>0$ にも $k$ があって、割合 $1-\varepsilon$ 以上を満たせる例と $\delta$ 以下しか満たせない例の区別が NP困難である、という Khot が 2002 年に提出した未解決の予想である。予想のもとでは、頂点被覆の比 $2$ や最大カットの比 $0.878\ldots$ が最良の近似比になる。2 対 2 定理(2018 年)から、割合が約 $1/2$ の例と小さい例の区別は NP困難である。
Unique Games予想(unique games conjecture)は、2 変数の制約で「一方の変数の値を決めるともう一方の値がちょうど 1 つに決まる」ものだけからなる制約充足問題について、ほとんどすべての制約を満たせる例と、ごく一部しか満たせない例とを見分けることが NP困難である、という予想である。Khot が 2002 年に提出した(WS11 p. 445、Kho10 p. 1)。予想は未解決である(KMS23 p. 4 による 2018 年の時点。WS11 第 17 章 p. 447 は 2011 年の時点でこれを近似アルゴリズムの分野の第一の未解決問題に挙げている)。
PCP定理 は、3CNF の充足可能性に「ギャップ」を作り、多くの問題の近似の難しさを導いた。しかし頂点被覆の比 $2$ や、半正定値計画による最大カットの比 $0.878\ldots$ のような、知られた算法の比がちょうど最良であることは、2018 年の時点で予想なしには示されていない(頂点被覆の比 $2$ を下回れるかは、2018 年の KMS23 p. 2 でも中心的な未解決問題とされている)。この予想を仮定すると、それらの比が最良であることが従う(thm-ugc-consequences)。予想は、多くの近似の限界を 1 つの問題に集約する仮説として働いている。
この記事では、Unique Games の例と予想を定義し、予想の形が必然であることを 2 つの命題で証明する。すべての制約を満たせるかどうかは多項式時間で判定でき(prop-ugc-perfect)、どの例でも割合 $1/k$ の制約は満たせる(prop-ugc-random)。そのため、予想の「ほとんどすべて」を「すべて」に替えたり、ラベルの数 $k$ を $1/\delta$ より小さくしたりすると成り立たない(cor-ugc-form)。次に、予想を仮定した帰結を述べ、2018 年に示された 2 対 2 定理(thm-ugc-22)から、満たせる割合が約 $1/2$ の例と小さい例の区別が NP困難であることを導く(cor-ugc-half)。
$[k]=\{1,\dots,k\}$ とする。グラフは有限で、多重辺を許し、辺を 1 本以上もつとする。
Unique Games の例 $\mathcal{U}=(G,[k],(\pi_e)_{e\in E})$ とは、グラフ $G=(V,E)$、ラベル の集合 $[k]$、各辺 $e$ に向き $e=(u,v)$ を 1 つ決めて与えた全単射 $\pi_e\colon[k]\to[k]$ の組である。写像 $L\colon V\to[k]$ を ラベル付け といい、$\pi_e(L(u))=L(v)$ のとき $L$ は辺 $e$ を 満たす という。$\mathcal{U}$ の 値 を
$$
\mathrm{val}(\mathcal{U})=\max_{L\colon V\to[k]}\frac{\#\{e\in E:L\text{ は }e\text{ を満たす}\}}{\lvert E\rvert}
$$
と定める(WS11 §13.3、pp. 344–345、Kho10 Definition 2.4、p. 5)。
辺の向きを逆にしたいときは $\pi_e$ を逆写像 $\pi_e^{-1}$ に替えれば同じ制約になる。「unique」は、$u$ のラベルを決めると $e$ を満たす $v$ のラベルがただ 1 つに決まり、逆も同じであることを指す。
$0< s< c\le1$ とする。$\mathrm{GapUG}_k(c,s)$ が NP困難 であるとは、どの $L\in\mathrm{NP}$ にも多項式時間で計算できる写像 $f$ があって、各入力 $x$ について $f(x)$ はラベルの集合が $[k]$ の Unique Games の例であり、$x\in L$ なら $\mathrm{val}(f(x))\ge c$、$x\notin L$ なら $\mathrm{val}(f(x))\le s$ となることをいう。
これは PCP定理 の記事のギャップ問題の定義と同じ形である。$\mathrm{GapUG}_k(c,s)$ が NP困難で P $\ne$ NP なら、Unique Games の例の値を $s/c$ より良い比で近似する多項式時間の算法はない。
量化の順序に注意する。まず $\varepsilon,\delta$ を与え、それに応じてラベルの数 $k$ を大きくとってよい。
ラベルを $\mathbb{Z}/k\mathbb{Z}$ とし、各辺 $(u,v)$ に「$x_u-x_v\equiv c_{uv}\pmod k$」の形の制約を置いた例を MAX 2LIN($k$) という。$\pi_e(i)=i-c_{uv}$ は全単射なので Unique Games の例である。予想はこの形の例に限っても同値であることが知られている(Khot・Kindler・Mossel・O'Donnell。WS11 Conjecture 16.44、p. 438 と p. 445。ラベルを $\mathbb{F}_2^\ell$、制約を $x_u+x_v=b$ とした形も同値:KMS23 Conjecture 1.2 と脚注 4、p. 4)。この記事では証明しない。
$n$ を奇数とし、長さ $n$ の閉路の全部の辺に ex-ugc-maxcut の制約を置く。すべての辺を満たすには隣り合う頂点の色を交互に変える必要があり、一周すると色が $n$ 回変わって元に戻らないので、値は $1$ でない。1 本の辺を除くと道になり、交互に塗ればその $n-1$ 本はすべて満たせるので、値は $(n-1)/n$ である。値が $1$ に近くても $1$ でない例はこのように簡単に作れる。
連結成分ごとに考えればよい。連結成分 $K$ の頂点 $r$ を 1 つ選び、$r$ のラベル $i\in[k]$ を 1 つ仮に決める。$K$ を $r$ から 幅優先探索 でたどり、ラベルの決まった頂点 $u$ から辺 $e=(u,v)$ でまだラベルのない $v$ に進むたびに、$v$ のラベルを $\pi_e(L(u))$ と決める(向きが逆なら $\pi_e^{-1}$ を使う)。全部決まったら $K$ の辺をすべて調べ、満たされない辺があれば次の $i$ を試す。
$K$ のすべての辺を満たすラベル付け $L^\ast$ があれば、$i=L^\ast(r)$ を試したとき、たどった木の辺に沿って帰納的に $L=L^\ast$ となる。各辺 $e=(u,v)$ では $v$ のラベルが $u$ のラベルから一意に決まるからである。したがってこの $i$ で検査は通る。逆に検査が通ればすべての辺を満たすラベル付けが得られている。1 つの $i$ あたりの手間は $K$ の頂点と辺の数に比例し、$i$ は $k$ 通りなので、全体で $O\bigl(k(\lvert V\rvert+\lvert E\rvert)\bigr)$ である。$\square$
どの Unique Games の例 $\mathcal{U}$ でも $\mathrm{val}(\mathcal{U})\ge1/k$ である(Kho10 p. 6)。
各頂点のラベルを $[k]$ から独立に一様に選ぶ。辺 $e=(u,v)$ が満たされるのは $L(v)=\pi_e(L(u))$ のときで、$L(u)$ を固定すると $L(v)$ はこの値に確率 $1/k$ で一致するので、$e$ が満たされる確率はちょうど $1/k$ である。期待値の線形性 から満たされる辺の数の期待値は $\lvert E\rvert/k$ で、確率変数はどこかで期待値以上の値をとるので、満たす辺が $\lvert E\rvert/k$ 本以上のラベル付けが存在する。$\square$
1:prop-ugc-random から値が $\delta$ 以下の例は存在しない。空の言語 $\emptyset\in\mathrm{NP}$ に対する写像 $f$ は、どの $x$ も $\emptyset$ に属さないので $\mathrm{val}(f(x))\le\delta$ をみたさなければならず、そのような $f$ はない。
2:NP困難なら、どの $L\in\mathrm{NP}$ についても $x\in L\iff\mathrm{val}(f(x))=1$ である($x\notin L$ なら値は $\delta< 1$)。右辺は prop-ugc-perfect により多項式時間で判定できるので $L\in\mathrm{P}$ となり、$\mathrm{NP}\subset\mathrm{P}$ である。$\square$
一意性を外すと事情が変わる。辺の制約を全射 $\pi_e\colon[m]\to[n]$(射影)に広げた 2 部グラフ上の問題(ラベル被覆)では、すべての辺を満たせる例と割合 $\delta$ 以下しか満たせない例の区別が、どの $\delta>0$ についても NP困難である(PCP定理 と Raz の並列反復定理による。Kho10 Definition 2.2・Theorem 2.3、pp. 3–4)。射影では $v$ のラベルから $u$ のラベルが決まらないので、prf-ugc-perfect の伝播が働かない。
conj-ugc-main が正しいとする。どの定数 $\varepsilon>0$ についても、次の多項式時間の算法があれば P $=$ NP である(WS11 Theorem 1.16、p. 28、Theorem 6.11、p. 147、Theorem 8.10、p. 207)。
この記事では thm-ugc-consequences を証明しない。1 は Khot・Regev(WS11 p. 34)、2 は Khot・Kindler・Mossel・O'Donnell と Mossel・O'Donnell・Oleszkiewicz の不変性原理による(WS11 p. 445)。予想なしに知られている限界と並べる。
| 問題 | 多項式時間で達成できる比 | 予想なしの NP困難性 | 予想を仮定した限界 |
|---|---|---|---|
| 最小頂点被覆 | $2$(近似アルゴリズム) | $10\sqrt5-21\approx1.36$ 未満は P $=$ NP(WS11 Theorem 1.15、p. 28)、$\sqrt2$ 未満も同様(KMS23 p. 6) | $2-\varepsilon$ |
| 最大カット | $\alpha_{\mathrm{GW}}\approx0.878$(半正定値計画) | $16/17\approx0.941$ を超える比は P $=$ NP(WS11 Theorem 6.10、p. 147) | $\alpha_{\mathrm{GW}}+\varepsilon$ |
| Unique Games(値 $1-\varepsilon$ の例) | 割合 $1-O(\sqrt{\varepsilon\log k})$ を満たす(WS11 Theorem 13.14、p. 351) | — | $1-\sqrt{2/\pi}\sqrt{\varepsilon\log k}+o(1)$ を超えるのは NP困難(同 Theorem 13.15、p. 351) |
さらに Raghavendra(2008)は、予想のもとで、どの制約充足問題でも近似の難しさの限界が自然な半正定値計画の緩和の整数性ギャップに一致することを示し、Raghavendra・Steurer はその比を達成する丸めを与えた(WS11 p. 445)。
予想からの帰着がどう働くかを、多重カットの場合の易しい向きで見る。多重カット問題とは、グラフと頂点の対 $s_i,t_i$ の列が与えられ、取り除くとすべての $s_i$ と $t_i$ が切り離される辺の集合のうち最小のものを求める問題である。
ex-ugc-2lin の例(グラフ $G=(V,E)$、定数 $c_{uv}$)から、頂点 $V\times\mathbb{Z}/k\mathbb{Z}$、辺 $\{(u,i),(v,j)\}$($uv\in E$、$i-j\equiv c_{uv}$)のグラフ $G'$ と、対 $\{(u,i),(u,j)\}$($i\ne j$)を作る。$G'$ の辺は $k\lvert E\rvert$ 本である。ラベル付け $x$ が $(1-\varepsilon)\lvert E\rvert$ 本以上の辺を満たせば、本数が $\varepsilon k\lvert E\rvert$ 以下の多重カットがある(WS11 Lemma 16.45、p. 438)。
$c\in\mathbb{Z}/k\mathbb{Z}$ ごとに $V_c=\{(u,x_u+c):u\in V\}$ とおくと、$V\times\mathbb{Z}/k\mathbb{Z}$ の分割になる。異なる組にまたがる辺をすべて取り除く。残りの連結成分はどれか 1 つの $V_c$ に含まれ、$V_c$ は各 $u$ について頂点を 1 つしか含まないので、$(u,i)$ と $(u,j)$($i\ne j$)は切り離される。
取り除いた辺 $\{(u,i),(v,j)\}$ では、$i=x_u+c$、$j=x_v+c'$、$c\ne c'$ で、$i-j\equiv c_{uv}$ だから $x_u-x_v\equiv c_{uv}+(c'-c)\not\equiv c_{uv}$ となり、$G$ の辺 $uv$ は満たされていない。満たされない辺 $uv$ は高々 $\varepsilon\lvert E\rvert$ 本で、それぞれに対応する $G'$ の辺は $k$ 本なので、取り除いた辺は $\varepsilon k\lvert E\rvert$ 本以下である。$\square$
逆向き(多重カットから値の大きいラベル付けを作る。WS11 Lemma 16.46、p. 439)と合わせると、多重カットの良い近似算法は MAX 2LIN($k$) のギャップを見分けることになり、thm-ugc-consequences の 3 が出る(WS11 §16.5)。
予想そのものは未解決だが、制約を「一方の値を決めるともう一方の値が 2 つに絞られる」形に緩めた問題では、対応する主張が証明された。
$\ell\ge1$ とする。2 対 2 の例 とは、$\mathbb{F}_2^\ell$ に値をとる変数 $x_1,\dots,x_n$ と、$m$ 個の制約の組である。各制約は異なる 2 変数 $x_i,x_j$ について
$$
T x_i+T'x_j\in\{b,b'\}
$$
の形をもつ。ここで $T,T'$ は $\mathbb{F}_2$ 上の可逆な $\ell\times\ell$ 行列、$b,b'\in\mathbb{F}_2^\ell$ で、制約ごとに異なってよい。値 $\mathrm{val}$ は、同時に満たせる制約の割合の最大値である(KMS23 Definition 1.3、p. 6)。
$b\ne b'$ なら、$x_i$ を決めると制約を満たす $x_j$ はちょうど 2 つあり、逆も同じである。
どの $\varepsilon>0$ についても、ある $\ell=\ell(\varepsilon)$ があって、値が $1-\varepsilon$ 以上の 2 対 2 の例と $\varepsilon$ 以下の例を見分けることは NP困難である(KMS23 Theorem 1.4、p. 6)。
この記事では thm-ugc-22 を証明しない。Khot が 2002 年に Unique Games予想と同じ論文で提出した予想(完全性 $1$ で、2 対 1 の制約の形)を、完全性 $1-\varepsilon$ の形で証明したものである。Khot・Minzer・Safra(2017)と Dinur・Khot・Kindler・Minzer・Safra(2016、2017)の論文、Barak・Kothari・Steurer、Khot・Safra、Khot・Minzer・Moshkovitz・Safra の寄与を経て、Grassmann グラフの擬似ランダムな集合の展開性の証明で完成した(KMS23 pp. 2–3、p. 6 の脚注 10)。論文は 2018 年に公開され、2023 年に刊行された。
$0< \varepsilon< 1/3$ を満たすどの $\varepsilon$ についても、ある $\ell$ があって、ラベルの数を $k=2^\ell$ として $\mathrm{GapUG}_k\bigl(\tfrac{1-\varepsilon}2,\varepsilon\bigr)$ は NP困難である。
$\ell=\ell(\varepsilon)$ を thm-ugc-22 のものとし、$\mathbb{F}_2^\ell$ を $[k]$ と同一視する。2 対 2 の例 $\mathcal{V}$(制約 $m$ 個)から、各制約 $Tx_i+T'x_j\in\{b,b'\}$ を 2 つの制約
$$
Tx_i+T'x_j=b,\qquad Tx_i+T'x_j=b'
$$
に替えた Unique Games の例 $\mathcal{U}$(辺 $2m$ 本)を作る。辺 $(i,j)$ の写像は $\pi(x)=T'^{-1}(b+Tx)$ で、$T,T'$ が可逆なので全単射である。この変換は多項式時間でできる。
値が大きい側。 $\mathcal{V}$ の制約の $1-\varepsilon$ 以上を満たす割り当てでは、満たされた 2 対 2 の制約ごとに、対応する 2 本の辺の少なくとも一方が満たされる。よって $\mathrm{val}(\mathcal{U})\ge(1-\varepsilon)m/(2m)=(1-\varepsilon)/2$ である。
値が小さい側。 $\mathrm{val}(\mathcal{V})\le\varepsilon$ とする。どの割り当てでも、$\mathcal{U}$ の辺が満たされればその元の 2 対 2 の制約も満たされ、1 つの制約から来る辺は 2 本なので、満たされる辺は $2\varepsilon m$ 本以下である。よって $\mathrm{val}(\mathcal{U})\le\varepsilon$ である。
$L\in\mathrm{NP}$ から 2 対 2 の例への写像(thm-ugc-22)にこの変換を合成すれば、def-ugc-gap の写像になる。$\square$
KMS23 Theorem 1.5(p. 6)は、常に満たされる制約を少し加えて完全性をちょうど $1/2$ にした形を述べる。この系は予想の完全性 $1-\varepsilon$ には届かない。それでも、cor-ugc-form の 1 が示すとおり $\delta$ が小さいことが本質的な部分であり、そこが証明された。同じ論文の流れから、最小頂点被覆の $\sqrt2$ 未満の比の近似が NP困難であることも従う(KMS23 §1.3.1、p. 6)。
予想が正しければ、値 $1-\varepsilon$ の例でも多項式時間では割合 $\delta$ しか保証できない。知られている算法は次のとおりである。
| 変える条件 | 反例・根拠 | 成り立たなくなること |
|---|---|---|
| 完全性 $1-\varepsilon$ を $1$ に | prop-ugc-perfect | NP困難性(P $\ne$ NP のもと。cor-ugc-form の 2) |
| ラベルの数 $k\ge1/\delta$ を $k< 1/\delta$ に | prop-ugc-random | NP困難性(仮定なしに。cor-ugc-form の 1) |
| 制約の一意性を射影に | Kho10 Theorem 2.3 | すべての辺を満たせるかの多項式時間の判定(prop-ugc-perfect の結論。P $\ne$ NP のもと) |
| cor-ugc-half の変換で、完全性 $1-\varepsilon$ を保つこと | $b\ne b'$ の 2 対 2 の例 | 作った Unique Games の例の値は $1/2$ 以下で、$1-\varepsilon$ に届かない |
3 行目:射影の制約の問題は、完全性 $1$、健全性 $\delta$ のギャップ版がどの $\delta>0$ でも NP困難である。P $\ne$ NP なら、すべての辺を満たせるかを多項式時間で判定する算法はない(あればギャップ版も解ける)。4 行目:$b\ne b'$ の 2 対 2 の制約 1 つから作った 2 本の辺は、同じ割り当てで同時には満たされない($Tx_i+T'x_j$ は $b$ と $b'$ の両方には等しくなれない)ので、どの割り当てでも満たされる辺は全体の半分以下である。この変換では予想そのものは出ない。
Unique Games の問題と予想は Khot が 2002 年の STOC の論文(On the power of unique 2-prover 1-round games、pp. 767–775)で導入した。もとは 2 部グラフの上の形で述べられた(WS11 p. 445 と文献 [192])。定義と予想の形は WS11 §13.3・§16.5 と Kho10 §2 に、2 対 2 定理とその帰結は KMS23 §1 に従った。prop-ugc-perfect と prop-ugc-random の議論は WS11 p. 345 と Kho10 p. 6 にあり、証明はこの記事で書き下ろした。cor-ugc-form、prop-ugc-multicut、cor-ugc-half の証明もこの記事で書き下ろした(prop-ugc-multicut は WS11 Lemma 16.45 の主張、cor-ugc-half は KMS23 p. 6 の説明に沿う)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する