2019年6月3日月曜日

グラフの直径と支配集合

グラフの頂点$v$の隣接点集合を$N(v)$とし, $S\subseteq V$に対して $N(S)=\bigcup_{s\in S} N(s)$ と定めます. グラフ$G=(V,E)$の頂点部分集合 $D\subseteq V$ は, $D\cup N(D)=V$ となるとき支配集合 (dominating set) であると言います. 言い換えると, 任意の$v\in V\setminus D$は$D$の何らかの頂点に隣接しているとき, $D$は支配集合となります.

グラフ$G$が入力として与えられたとき, $G$がサイズ$k$の支配集合を持つかどうかを判定する問題は($k$も入力で与えられるとき)NP-完全となり, $k$をパラメタとみなしたときはW[2]-困難となります. 全探索だと $O(n^{k+1})$時間で解けますが, $k=2$の時は$O(n^\omega)$時間で解けます ($\omega\leq 2.373$は行列積の計算時間の指数).

グラフ$G$がサイズ2以下の支配集合を持たないと仮定しましょう. すると, 任意の二頂点$v_1,v_2\in V$に対して, $v_1$と$v_2$のどちらとも隣接しない頂点$w\in V\setminus \{v_1,v_2\}$ が存在することになります. では, $G$の補グラフ $\bar{G}$ を考えてみましょう. すると前述の条件は, 任意の$v_1,v_2\in V$に対してある$w\in V\setminus \{v_1,v_2\}$が存在して$w$は$v_1$と$v_2$のどちらとも隣接している, というものになります. 言い換えると任意の二頂点間には長さ2のパスがあるということを意味するため, 直径が2以下である, ということになります. したがって補グラフの直径が2以下かどうかを判定すればよく, これは隣接行列の二乗を計算すれば終わるので$O(n^{\omega})$時間で判定できるわけです. 逆に, $G$の直径が$2$以下の場合はその補グラフがサイズ$2$以下の支配集合を持たないことも言えます. この観察をまとめると,
$G$はサイズ$2$以下の支配集合を持たない iff 補グラフ$\bar{G}$の直径は2以下.

この記事の本質的な部分は以上となるのですが, 折角なのでこの事実を使って次の定理を証明しようと思います.

定理1.
任意の$d\geq 3$に対して, $d^2$頂点を持つ$(d^2-d-1)$-正則グラフはサイズ$2$の支配集合を持つ.

証明.
背理法で示します. $d^2$頂点の$(d^2-d-1)$-正則グラフでサイズ$2$以下の支配集合を持たないものが存在すると仮定し, そのグラフを$G$とします. $G$の補グラフ$\bar{G}$は $d^2$頂点を持つ$d$-正則グラフとなり, 上記の事実により$\bar{G}$の直径は$2$となります (直径=1 iff 完全グラフなので, 直径=2になる).

ところが, $d$-正則グラフで頂点数=$d^2$かつ直径=2となるものは長さ4の閉路以外に存在しない[1]ため, $d\geq 3$に矛盾 (証明終).

文献[1]の結果の証明はこちらの記事のように, 隣接行列の固有値の多重度などを考えれば得られます. 文献[1]のページ数は4ページしかなく読むのにそれほど時間がかからないと思うので興味のある方はぜひ読んでみてください.

定理2. 
任意の$d\not\in\{2,3,7,57\}$に対して, 任意の$d^2+1$頂点 $(d^2-d)$-正則グラフはサイズ$2$の支配集合を持つ.

証明.
定理1の証明とほぼ同じです. $d^2+1$頂点, $(d^2-d)$-正則でかつサイズ$2$の支配集合を持たないグラフ$G$が存在するならば, その補グラフ $\bar{G}$は$d^2+1$頂点$d$-正則グラフでしかも直径=2となります. このようなグラフは Moore graph 以外に存在しないので, $d\in \{2,3,7,57\}$ となるので矛盾です (証明終).


[1] P. Erdős, S. Fajtlowicz, A. J. Hoffman. Maximum degree in graphs of diameter 2, Networks, Vol. 10, Issue. 1, 1980.

2019年6月2日日曜日

Schwartz-Zippelの脱乱択化 ⇒ 回路計算量下界

計算量理論の主要な分野の一つに回路計算量というものがあります. これはなぜメジャーなのでしょう?

判定問題を解くアルゴリズムを実行しているチューリング機械は回路によって表現できます. 実行時間 $T$ のアルゴリズムはサイズ $O(T\log T)$ の回路によって模倣することが出来ます. 具体的にはチューリング機械の「1ステップ模倣回路」を構築し, これを $T$ 段積み重ねれば所望の回路が得られます. いわば, 回路は計算を模倣するモデルであるため, その研究は計算の本質を掴む良いアプローチになるというわけです.

さて, 多項式時間アルゴリズムの動作は多項式サイズの回路によって模倣できる (専門用語で言うとP $\subseteq $ P/poly が成り立つ) ので, 対偶をとると「多項式サイズ回路で解けない問題は多項式アルゴリズムで解けない」ことが言えます.

多項式時間アルゴリズムで解ける判定問題のクラスはPと呼ばれますが, 多項式サイズの回路で解ける判定問題のクラスは P/poly と呼ばれます. もう少しちゃんと言うと, 判定問題とは言語 $L \subseteq \{0,1\}^*$ のことであり, インスタンス $x\in\{0,1\}^*$ に対して $x\in L$ か否かが問われます. 言語 $L$ は以下の条件を満たすとき, P/poly に属すると言います:

(条件) ある回路族 $\{C_n\}_{n\in\mathbb{N}}$ が存在して, 各$n$に対して$C_n$の素子数は$n$の多項式で上から抑えられており, さらに任意の$x\in\{0,1\}^*$ に対して $C_{|x|}(x)=1$ iff $x\in L$ が成り立つ. ここで $|x|$ は$x$の文字数.

冒頭に述べたように, (チューリング機械上の)多項式時間アルゴリズムは多項式サイズの回路によって模倣できるため, PはP/poly に含まれます. この包含関係はstrictで, 以下に示すように, 実はP/polyは計算不可能な判定問題も含んでいます:

: ビット列 $x\in \{0,1\}^n$ とチューリング機械が一対一対応することが知られています (チューリング機械全体は加算無限個). そこで, 自然数$n$に対してその二進表記に対応するチューリング機械を$M_n$と表すことにします. さて, 言語 $L$ として $L=\{1^n: M_n$ は任意の入力に対して停止する $\}$ と定めます. このとき $L\in $P/polyが成り立ちます. 実際, $C_n$として, $x=1^n$かつ$M_n$が停止するならば $C_n(x)=1$, そうでないならば $0$ を出力する回路とすると, $C_n$のサイズは $O(n)$ です ($M_n$が停止するかどうかは神様が知っていて, その神様が各$n$に対して$C_n$を設計してくれた, と思ってください. クラスP/polyでは, 回路族の存在性を要請しているのであってその回路族がチューリング機械によって構成できかどうかは要請していません!). すると $C_n$ は $L$を解くので, $L\in $P/polyとなります.


回路計算量理論では, 色んな問題に対してその問題を解く回路のサイズはどれくらいなのかを研究しています. 具体的には問題クラスの回路下界や, 回路のタイプを制限 (単調回路など) したときの回路下界などが研究されています.

前置きが長くなりましたが, 本記事では脱乱択化と回路計算量下界の関係について概説します.


 ZEROPの脱乱択化


与えられた多変数多項式 $P(x_1,\ldots,x_n)$ が恒等的に $0$ かどうかを判定する問題をZEROP と呼びます. ここで入力は以下の例のように算術回路で与えられるものとします.




この問題はランダムな値を代入したときに$0$になるかどうかを確認し, これを繰り返すことにより, with high probability で解くことができます (例えばこの記事で紹介されているSchwartz-Zippelの補題を参照してください). 実は, ZEROPはクラスPに属するか否かは未解決です (計算量理論ではpseudorandom generatorが存在し即ちP=BPPであると信じられているため, ZEROPはクラスPに属するだろうと信じられています).

Schwartz-Zippelの補題が脱乱択化できればZEROPも脱乱択化できてハッピーなのですが, ZEROPの脱乱択化に関して以下の結果が知られています:

定理1 [Kabanets Impagliazzo, 2003]
以下の三つの主張のうち, 少なくとも一つは偽である.
(1). ZEROPはクラスPに属する.
(2). 01行列のパーマネントは多項式サイズの算術回路で解ける.
(3). NEXP $\subseteq$ P/poly.

それぞれの主張を見ていきます. (1)は上記の通りで, ZEROPが脱乱択化出来るということを意味します. (2)は読んだままです. 多項式サイズの算術回路で解けるというのはP/polyの算術回路版のような意味です. 普通の回路では各ゲートに and か or が記されていますが算術回路では + , -, × のいずれかが記されており, 出力ゲートからは期待した値が出てくるようなものです (そのため, 計算途中のビット長などは気にしません). (3)のNEXPというのはNPの指数時間verです. NPは非決定的チューリング機械で多項式時間で解ける問題のクラスですが, NEXPは非決定的チューリング機械で指数時間 (i.e., $2^{\mathrm{poly}(n)}$時間) で解ける問題のクラスです. なので, P$\subseteq$NPと同様にEXP$\subseteq$NEXPが成り立ちますが, EXP$\neq$NEXPかどうかは未解決です (P$\neq$NPならばEXP$\neq$NEXPが直ちに従います).

つまり, 定理1より, ZEROPが脱乱択化できたら, either パーマネントは多項式サイズの算術回路で計算できない or NEXPというクラスは多項式サイズの回路で解けないことが分かるため, 回路計算量の下界が得られたことになります. これが脱乱択化によって示される回路計算量下界ということになります.

定理1の証明を全て網羅しようとすると, pseudorandom generator, 対話証明 (クラスMAとか), IP=PSPACE, 戸田の定理, 非決定性の時間階層定理, easy witness lemmaといった多くの前提知識が必要となりとても大変です. なので本記事では計算量クラスには出来るだけ触れず, なぜパーマネントやZEROPが登場するかについて重きをおいた議論について概説したいと思います.

以下の補題を考えます. 専門用語が多いので, 下に概説を付け加えました.

補題1.
NEXP $\subseteq$ P/poly ならば, NEXP=EXP.

補題2 (非決定性チューリング機械の時間階層定理).
NEXP ≠ NP.

補題3 (Meyerの定理).
$\Sigma_2$を,  $\exists x\forall y: \phi(x,y)$  の判定問題として表せる問題のクラスとする ($\phi$は論理式). このとき, $\mathrm{EXP}\subseteq \mathrm{P}/\mathrm{poly}$ ならば $\mathrm{EXP}=\Sigma_2$.

補題4 (戸田の定理の特殊ケース).
$\Sigma_2\subseteq \mathrm{P}^{\mathrm{perm}}$.

補題1は, easy witness lemma (IKW02) と呼ばれる面白い結果から従うのですが, その証明をしようとするとpseudorandom generator, クラスMAなどの説明から始めなくてはならずとても大変なので本記事ではそこまでしません. 補題2は時間階層定理の非決定性verです. 証明は決定性の時と同じようにはいかず, 少し難しいです. 補題3における$\Sigma_2$とは多項式時間階層の一つです. 例えばNPの問題は多項式長の証拠が存在するような問題なので, $\exists x:\phi(x)$ という形で書けるのですが, ここに出てくる量化子を交互に繰り返した問題を考えることで多項式時間階層  (PH: polynomial hierarchy) が構成されます. もう少しちゃんと言うと, 量化子が有限回交互に繰り返された形で書ける問題のクラスをPHと呼びます. ちなみに, coNPという計算量クラスは $\forall x: \phi(x)$ の形で書けるものであり, $\exists$と$\forall$を入れ替えたものとして解釈できるため, coNP$\subseteq$ PHです. $\mathrm{P}^{\mathrm{perm}}$とは, 行列のパーマネントを計算するオラクルを用いて多項式時間で判定できる問題のクラスです (厳密には, 行列$A$とインデックス$i$を受け取り, $A$のパーマネントの第iビット目が0か1かを判定するというオラクルを持ったチューリング機械で多項式時間で判定出来る問題のクラスです). 戸田の定理は PH$\subseteq \mathrm{P}^{\mathrm{perm}}$ を主張しており, 戸田 誠之助先生によって1981年に発表されました. この定理は計算量理論において非常に重要な定理として知られています. とても面白い解説がこちらにあるので, 興味のある方はぜひ目を通してみてください. 上に述べた補題はどれも重要な結果なので補題というよりそれ自体が定理になるような結果です. 本記事では補題1~4を認めて定理1の証明を行います.

定理1の証明.
主張(1)~(3)が成り立つと仮定するとNEXP=NPになってしまい補題2に反する, という流れで証明します. まず

主張(1),(2)⇒$\mathrm{P}^{\mathrm{perm}}\subseteq \mathrm{NP}$

を示します. まず, $\mathrm{P}^{\mathrm{perm}}$ に属する問題Xに対して多項式長の証拠があることを言います. この問題Xはパーマネントをオラクルとした多項式時間アルゴリズムで解くことが出来るので, オラクル呼び出しの部分をパーマネントを計算する多項式サイズの回路に置き換えることができます (c.f. 主張(2)). より正確には, 主張(2)より行列のパーマネント計算は多項式サイズの回路の族$\{C_n\}$で解くことが出来るため, この回路を表現するビット文字列をwitnessとして与え, そのwitnessで得られた回路をオラクル呼び出しの部分に置き換えることで問題Xを解きます. このとき, NPに属することをちゃんと証明するためには, この記事にあるように, witnessで与えられた回路が本当にパーマネントを計算しているかどうかをチェックする必要があります. このチェックする部分で主張(1)を用います.

今, 算術回路族$\{C_i\}$を持っていて ($i\leq \mathrm{poly}(n)$), 各$C_i$が本当にサイズ$i\times i$の行列のパーマネントを計算するかどうかをチェックしたいとしましょう. 明らかに$1\times 1$行列のパーマネント計算の回路のチェックは簡単です. さて, $C_1,\ldots,C_t$がそれぞれ正しいとしたとき, $C_{t+1}$の正当性のチェックを行うアルゴリズムを考えます. $A$を$(t+1)\times (t+1)$行列として, その$1$行目と$j$列目だけを除去して得られる$t\times t$行列を$A_{1,j}$とします (下図参照).




$\mathrm{perm}(M)$ で行列 $M$ のパーマネントを表すとします. すると, 行列式の展開と同じ要領で, $\mathrm{perm}(A)=\sum_{j=1}^{t+1} \mathrm{perm}(A_{1,j})$ が成り立つことが分かります. 今, 行列$A$を引数として持つ多項式

$P(A):=\sum_{j=1}^{t+1}C_t(A_{1,j})-C_{t+1}(A)$ ..........(*)

を考えます. 各回路$C_t,C_{t+1}$は算術回路として表現されているので多項式になっていることに注意してください. 帰納法の仮定より, $C_t(A_{1,j})=\mathrm{perm}(A_{1,j})$なので, $C_{t+1}$がパーマネントを正しく計算する iff $P(A)$は恒等的に$0$. したがって$(t+1)^2$変数多項式 $P$ に対して ZEROP を解くことによって, witnessとして与えられた回路族 $\{C_t\}$ が正しくパーマネントを計算するかどうかをチェックすることが出来るので, $\mathrm{P}^{\mathrm{perm}} \subseteq \mathrm{NP}$ が成り立ちます.

EXP$\subseteq$NEXPなので, 主張(3)より, EXP$\subseteq$P/polyです. したがって

主張(3)⇒$\mathrm{NEXP}=\mathrm{EXP}$.
主張(3) & 補題3 ⇒$\mathrm{EXP}\subseteq \Sigma_2$.
補題4 & 主張(*)⇒$\Sigma_2 \subseteq \mathrm{P}^{\mathrm{perm}} \subseteq \mathrm{NP}$.

これらを組み合わせると, 主張(1)~(3) ⇒ $\mathrm{NEXP}\subseteq \mathrm{NP}$ となり, 補題2と矛盾が生じます. よって主張(1)~(3)が全て真になることはありません.




参考文献


S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press.

2019年6月1日土曜日

閉路検出問題の計算複雑性

グラフ $H$ を固定し, $H$-Detection という問題を考えます. この問題はグラフ $G$ が入力で与えられたときに $G$ が $H$ を部分グラフとして含むかどうかを判定する問題です.
例えば, $H$ が長さ$|V(G)|$ の閉路だとするとこれはハミルトン閉路問題になるのでNP-困難です. 一方で $H$ が辺数 $|V(G)|/2$ のマッチングならば完全マッチングを含むかどうかの判定問題になるので, 多項式時間で解けます. それでは, どのような$H$に対して $H$-Detection は多項式時間で解けるのでしょうか?

この話はグラフアルゴリズムの分野でよく研究されている分野であり, 結論から言うと未解決なのですが, $H$のサイズをパラメータとしたときに$H$-Detectionは「木幅がunbounded ならばW[1]-困難である」という予想が有ります[1] (逆に木幅がboundedならばcolor codingでFPT時間で解けます). 本記事では $H$を様々な長さの閉路としたときどのような結果が知られているかについてまとめていきます. 基本的に$n=|V(G)|$, $m=|E(G)|$ とします.

$k$-cycle


一般の$k$に対しては color coding というアルゴリズムによって, $2^{O(k)}\cdot n^{\omega}$時間で解けます ($n\times n$の行列積が$O(n^{\omega})$ 時間でできるとします. 2019年6月1日現在では, $\omega\approx 2.373$ です).

$k$が定数だとしましょう. 実は, 現状では$k$の偶奇によって計算量が変わります. $k$が奇数のときはこれまで知られている最速のアルゴリズムは $O(n^{\omega})$ 時間です. 例えば $k=3$ の場合は隣接行列の3乗を計算して体格成分だけを見れば良いですね. 一方で$k$が偶数のときは, $O(n^2)$で解くアルゴリズムが知られています[2]. 例えば$k=4$の時は以下の単純なアルゴリズムで四角形を見つけることができます. ただし $N(u)$は頂点$u$の隣接頂点の集合とします.





このアルゴリズムでは配列 $\mathrm{T}[i][j]$ は二頂点$ij$間の長さ2のパスをカウントしていて, もし$\mathrm{T}[i][j]\geq 2$ なる$ij$が見つかったらその瞬間に四角形が有ると判定してアルゴリズムを終了します. 配列$\mathrm{T}$の各要素は高々2回しかアクセスされないはず (2回アクセスしたらその瞬間にアルゴリズムはtrueを返して終了する) なので, 計算時間は$O(n^2)$になるわけです.

また, 辺数$m$に関しては近年にもう少し早いアルゴリズムが知られていたり[2]して, 自分が把握する限りをまとめるとこんな感じになります.



ハミルトン閉路

ハミルトン閉路はTSPで使うDPを考えると$O(2^n n^2)$時間で解くことができるのですが, それでは$O(1.99^n)$時間で解けるのでしょうか? (乱択を許せば)できることが知られています[4]. アルゴリズムではまず, 入力のグラフ$G$を使ってある多変数多項式 $P$ を構成し, $P$が恒等的に$0$かどうかを乱択で判定するというものです. ここで構成する多項式$P$は, 「$P$が恒等的に0 iff グラフがハミルトン閉路を持つ」という性質を満たすようなものを上手く構成します. したがって多項式が恒等的に0かどうかの判定が出来る決定的アルゴリズムがあればハミルトン閉路の検出も決定的に出来るようになります. CyganらによるFPT algorithmの本[5]の10.4.2に分かりやすく解説されているので興味のある方はどうぞ.

[1]. M. Grohe, The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 2007.
[2]. R. Yuster and U. Zwick, Finding even cycles even faster, SIAM J. Discrete Math, (1997).
[3] S. Dahlgaard, M. B. T. Knudsen, M. Stöckel, Finding even cycles faster via capped k-walks, In Proc. of STOC2017.
[4]. A Björklund, Determinant sums for undirected Hamiltonicity, SIAM J. COMPUT., 2014.
[5]. M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer Publishing Company, 2015.

2019年1月20日日曜日

離散確率空間上の確率集中不等式

本来, 確率変数は「ランダムな値をとる」ものであり, その挙動を予想することは困難です. しかし「n個の確率変数の和」といった幾つかのタイプの確率変数は「大体このくらいの値を高確率でとる(集中する)」ことが理論的に保証できます. この議論は確率集中不等式を用いてなされるものであり, 物理学, 機械学習, 計算機科学 (特に乱択アルゴリズムの解析), グラフ理論といった非常に広範囲な分野の理論的支柱の一つとなっています. 今回は離散確率空間上で成り立ついろんな確率集中不等式について紹介します.

この記事で紹介するのは Chernoff bound, Jansonの不等式, Kim-Vu polynomial concentration です. よくある確率集中不等式の本や連続の世界では Bernsteinの不等式, Azumaの不等式, Talagrandの不等式などが出てきますが, それらはここでは割愛します. Talagrandの不等式についてはめちゃくちゃ面白いので機会があれば紹介したいと思っています.

1. Chernoff bound


独立な確率変数の和の集中性を示す結果で, もっとも代表的なものです. $X_1,\ldots,X_n$を$[0,1]$の値をとる独立な確率変数で, $\mathrm{E}[X_i]=p_i$, $S=X_1+\cdots+X_n$, $\mu=E[S]$とします.

定理1 (Chernoff bound).
任意の $t>0$ に対して
$\Pr[S\geq \mu+t] \leq \exp\left(-\frac{t^2}{2(\mu+t/3)}\right)$.
任意の $t\leq \mu$ に対して
$\Pr[S\leq \mu-t] \leq \exp\left(-\frac{t^2}{2(\mu-t/3)}\right)$.


系2.
任意の$\epsilon>0$に対して,
$\Pr[S\geq (1+\epsilon)\mu] \leq \exp\left(-\frac{\min\{\epsilon,\epsilon^2\}\mu}{3}\right)$
及び
$\Pr[S\leq (1-\epsilon)\mu] \leq \exp\left(-\frac{\epsilon^2 \mu}{2}\right).$


Remark.
しばしば, $\Pr[S\geq (1+\epsilon)\mu] \leq \exp\left(-\Omega(\epsilon \mu)\right)$ などと勘違いされますが, これは $\epsilon\geq 1$ でないと成り立ちません. また, Chernoff boundには Hoeffidingなどいろんな亜種が知られていて, [1, 2]などが詳しいです. 特に

定理3.

独立なベルヌーイ試行 $X_1,\ldots,X_n$ に対して, $S=X_1+\cdots+X_n$, $\mu=\mathrm{E}[S]$とおく. 任意の $R\geq 2\mathrm{e}\mu$に対して
$\Pr[S\geq R]\leq 2^{-R}$
が成り立つ.

という結果も知られています[2, Corollary 10.4].

1.1. Chernoff bound の証明 (途中まで)



Chernoff boundの証明は初見だとビックリするようなアイデアに基づくものになっており, マルコフの不等式 ($\Pr[X>a]\leq \mathrm{E}[X]/a$) を使います. 概略だけ述べると

$\Pr[S\geq\mu+t] = \Pr[\exp(\lambda S)\geq \exp(\lambda(\mu+t))] \leq \exp(-\lambda(\mu+t))\mathrm{E}[\exp(\lambda S)]$

for any $\lambda\geq 0$ なので, 右辺の $\mathrm{E}[\exp(\lambda S)]$ を上から抑えることを考えます. ここで$S$は独立確率変数の和なので, 積に分解でき

$\mathrm{E}[\exp(\lambda S)]=\prod_{i=1}^n \mathrm{E}[\exp(\lambda X_i)] = \prod_{i=1}^n (1-p_i(1-\mathrm{e}^{-\lambda}))$

となります. (個人的には$\exp(\lambda S)$を考えるあたりがビックリポイントなのですが, モーメントなどをよくよく考えるとなんとなく自然に感じられるようになります). あとはこの右辺を気合いで上から抑えます. 具体的には

$\exp(\lambda x)\leq 1-x+x\exp(\lambda)$ for $x\in[0,1]$

という不等式を使います. この先は式変形を頑張って整理するだけです. 詳しく知りたい方は, 例えば [3, 21.4節] などをご覧ください.




2. Janson の不等式



Erdős–Rényiグラフ $G(n,p)$ を考えます. ここで$G(n,p)$ とは $n$ 頂点のグラフで各辺が独立に確率 $p$ で接続されて得られたグラフのことです. このグラフに含まれる三角形の個数を $Y$ とします. また, 辺$e$に対し, $X_e$を「$G(n,p)$が$e$を含んでいたら $1$, そうでなければ $0$」と定めます. すると

$Y=\sum_{u,v,w} X_{uv}X_{vw}X_{wu}$

と表せます. 一見すると確率変数の和なので Chernoff bound を使えば集中性が示せそうな気がしますが, 一般に $X_{uv}X_{uw}X_{wu}$と$X_{u'v'}X_{v'w'}X_{w'u'}$ は辺素でない限り独立じゃないのでChernoff boundは使えません. ただ, 辺素な三角形のペアは非常にたくさんあり, 従属関係がスパースなので集中性が示せるんじゃないかという気がします. このように独立な01確率変数上で従属関係がスパースな indicator の和に対し非常に強い下界を与えるのが Janson の不等式です. ちなみにLovász local lemmaも似たような設定を考えてます.

より一般に述べるために, 次の設定を考えます:
有限集合 $E$ で添字づけられた01確率変数の族 $(X_e)_{e\in E}$ を考えます. $\mathrm{E}[X_e]=p_e$ とし, 相異なる $e,f\in E$ に対して $X_e$ と $X_f$ は独立であるとし. $E$上の部分集合族 $\mathcal{E}\subseteq 2^E$ に対して確率変数 $Y_{\mathcal{E}}$ を

$Y_{\mathcal{E}}=\sum_{F\in\mathcal{E}} \prod_{e\in F} X_e$

と定めます. 三角形の例だと, $E$は$\binom{n}{2}$通りの辺の全体$\binom{V}{2}$であり, $X_e$ は $G(n,p)$ が辺$e$を含んでいるかどうかの indicator です. また, $\mathcal{E}$ は集合で書くと

$\mathcal{E}=\{\{a,b,c\}:a,b,c\in E$ are distinct. $\}$

です. すると $Y_{\mathcal{E}}$ は $G(n,p)$が含む三角形の個数になります.


定理4 (Jansonの不等式).

任意の $t>0$ に対し以下が成り立つ:

$\Pr[Y_{\mathcal{E}}\leq \mathrm{E}[Y_{\mathcal{E}}]-t] \leq \exp\left(-\frac{t^2}{\nabla}\right)$.

ここで $\nabla$は

$\nabla=\sum_{F_1,F_2\in\mathcal{E}:\,F_1\cap F_2\neq\emptyset} \mathrm{E}[\prod_{e\in F_1\cup F_2} X_e]$.


2.1. 三角形の個数の下界の導出


$\mathcal{E}$を, 冒頭で述べたように三角形の辺集合の全体と定めます. まず期待値 $\mathrm{E}[Y_\mathcal{E}]$を評価してみると,

$\mathrm{E}[Y_{\mathcal{E}}]=\binom{n}{3}p^3\approx \frac{(np)^3}{6}$

が得られます. 次に定理4に出てくる $\nabla$ を評価します. 式はややこしそうに見えますがやることは簡単で, 辺を共有する二つの三角形$F_1,F_2$に関して $p^{|F_1\cup F_2|}$ を足しあげるだけです. 実際, indicatorの期待値は確率と等しく, 総和の中の $\mathrm{E}[\prod_{e\in F_1\cup F_2} X_e]$ は今回の例でいうと $F_1$と$F_2$の辺が全て $G(n,p)$ に現れる確率と等しくなるので, $p^{|F_1\cup F_2|}$ となります.

ここで $F_1,F_2$ は辺を共有するので, $|F_1\cup F_2|\leq 5$です. そこで三つの場合を考えます:
(i). $|F_1\cup F_2|=3$ の場合: このとき, $F_1=F_2$は同じ三角形を表すので, このような組$(F_1,F_2)$は全部で $O(n^3)$ 通りあります.

(ii). $|F_1\cup F_2|=4$ の場合: そもそも辺を共有する三角形で$|F_1\cup F_2|=4$となるものは存在しません.

(iii). $|F_1\cup F_2|=5$ の場合: $F_1$は三角形の全体$\mathcal{E}$から選ばれるので, $O(n^3)$通りの選び方があります. 一方で$F_2$は$F_1$と一本だけ辺を共有するため, 下図のような感じになります. すると $F_2$ の頂点の自由度は $1$ なので, $F_1$を固定したとき$F_2$は $O(n)$ 通りしかとれません. 従って組 $(F_1,F_2)$ は$O(n^4)$通りです.
Case (iii) における二つの三角形 $(F_1,F_2)$ に対して $F_1\cup F_2$ が表すグラフ.


以上より, $\nabla$は

$\nabla = O(n^3)p^3+O(n^4)p^5 = O(n^3p^3(1+np^2))$

となります. これを定理4 に代入すると,

$\Pr\left[Y_{\mathcal{E}} \leq \mathrm{E}[Y_{\mathcal{E}}]-t\right] \leq \exp\left(-\Omega\left(\frac{t^2}{(np)^3(1+np^2)}\right)\right)$

が得られます. 例えば $t=\mathrm{E}[Y_{\mathcal{E}}]\approx \frac{(np)^3}{6}$を代入すると,

$\Pr[G(n,p)$が三角形を含まない$]\leq \exp\left(-\Omega\left(\frac{(np)^3}{1+np^2}\right)\right) \leq \exp(-\Omega((np)^2))$

となるので, $p\geq \Omega(n^{-2/3})$ならば, $G(n,p)$ は指数的に高い確率で三角形を含む, ということが結論づけられます.

Remark.

実は Janson の不等式は多くの場合で指数部分が定数倍を除くとタイトなバウンドを与えていることが知られており[5], 非常に強力な不等式であることがわかります.

備忘録.

証明はChernoff boundと同様に $\mathrm{E}[\exp(-\lambda Y)]$ のバウンドをうまく与えるのですが, 独立性が成り立たないのが辛いポイントで, 「とりあえず$\lambda$で微分」「アイテム$e$を固定し, $X_e$と独立な部分和とそうでない部分和に分けて, 独立でない部分和に関してはFKG不等式を使ったり」などを工夫します.



3. The Kim-Vu polynomial concentration



文献[4]で示された定理を紹介します. 一般的な呼称がわからないのですが自分はとりあえず表題の通り呼んでいます. 2節で用いたセッティングをここでも流用します. すなわち, 台集合 $E$ 上の独立01確率変数 $(X_e)_{e\in E}$ と部分集合族 $\mathcal{E}\subseteq 2^E$ に対して, 新たな確率変数

$Y_{\mathcal{E}}=\sum_{F\in\mathcal{E}} w_F\prod_{e\in F} X_e$

の集中性を考えます. ここで $w_F>0$ は重みです. 2節では Janson の不等式を用いて下界だけ示しましたが, この節では集中性を述べる結果を紹介します. 上界も求められるためJansonより汎用性は高いように見えますが, 得られるバウンド自体は Janson よりも少し弱い結果になります.

ここでは, $Y_{\mathcal{E}}$ は $X_e$ を変数として見たとき多変数多項式になっていることに着目します. この節で紹介する定理は, この多項式の次数が小さいときに有効な結果になります.

準備として, 縮約について述べます. 部分集合 $A\subseteq E$ に対して, 確率変数 $Y_A$ を

$Y_A=\sum_{F\in\mathcal{E}:A\subseteq F} w_F \prod_{e\in F\setminus A} X_e$

と定めます. $A$を含むような$F$について, $A$以外の要素を掛けて足し上げているので, $Y_A$ は $Y_{\mathcal{E}}$ の $A$による縮約とみなすことができます.

例えば $\mathcal{E}$ を 前節で考えた三角形をなす辺集合の族とし, $A=\{\{1,2\}\}$ を辺$12$のみからなる集合としましょう (今は大集合$E$は$\binom{n}{2}$個の辺集合であることに注意). すると, $Y_A$ は辺$\{1,2\}$を含む三角形 $F$ に対して 辺$\{1,2\}$を除去して足し上げたものになっているため,

$Y_A = \sum_{u\in V\setminus\{1,2\}} X_{1,u}X_{2,u}$

となります. イメージとしては $G(n,p)$ が 辺集合$A$ を含むという事象を条件つけたときの $Y_{\mathcal{E}}$ を表しています.


定理5 (The Kim-Vu polynomial concentration).

$Y_{\mathcal{E}}$ を $k$ 次多項式とする. すなわち, 任意の $F\in\mathcal{E}$ に対して $|F|\leq k$ が成り立つとする. $a_k=8^k\sqrt{k!}$とし,
$\Xi(\mathcal{E})=\max_{A\subseteq E}\mathrm{E}[Y_A]$,
$\Xi'(\mathcal{E})=\max_{\emptyset\neq A\subseteq E}\mathrm{E}[Y_{A}].$
と定める. 任意の$\lambda>1$に対して

$\Pr\left[|Y_\mathcal{E}-\mathrm{E}[Y_{\mathcal{E}}]|\geq a_k \sqrt{\Xi(\mathcal{E})\Xi'(\mathcal{E})}\lambda^k\right]\leq O(\exp(-\lambda+(k-1)\log n))$

が成り立つ.


3.1. $G(n,p)$ が含む三角形の個数の集中性



三角形の個数は $Y_{\mathcal{E}}$ として表せるため, 定理5により集中性が示せます. $A\subseteq E$に対して $\mathrm{E}[Y_A]$ を評価する必要がありますが, $A$を一辺 $\{1,2\}$ のみからなる集合のとき, 冒頭の例で述べた事実を使うと

$\mathrm{E}[Y_A]= \sum_{u\in V\setminus \{1,2\}} p^2 = O(np^2)$

となります. $A=\{\{1,2\},\{1,3\}\}$ ならば, $A$を含む $F$ としては三角形123しかありえないので, $\mathrm{E}[Y_A]=p$ です. つまり, $A$は増えれば増えるほど $Y_A$ は減っていく一方なので, 

$\Xi(\mathcal{E})=\max_{A\subseteq E}\mathrm{E}[Y_A]=O(n^3p^3)$,
$\Xi'(\mathcal{E})=\max_{\emptyset\neq A\subseteq E}\mathrm{E}[Y_{A}]=O(np^2)$

が成り立ちます. これを定理5に突っ込むと

$\Pr\left[|Y_{\mathcal{E}}-\mathrm{E}[Y_{\mathcal{E}}]|\geq  \Theta(n^2p^{2.5})\lambda^3\right] \leq O(\exp(-\lambda+2\log n))$

となります. 例えば $\lambda=3\log n$ を代入すると, 確率 $1-O(n^{-1})$ で

$\frac{(np)^3}{6}-O(n^2p^{2.5}(\log n)^3) \leq $三角形の個数 $\leq \frac{(np)^3}{6}+O(n^2p^{2.5}(\log n)^3)$

が成り立つことが簡単に示せます.


[1]. Concentration Inequalities and Martingale Inequalities: A Survey, F. Chung, and L. Lu, Internet Mathematics Vol. 3, No. 1: pp. 79-127 (2006).

[2]. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics, B. Doerr, arXiv:1801.06733, (2018).

[3]. Introduction to Random Graphs, A. Frieze, and M. Karoński, Cambridge University Press, (2016).

[4]. Concentration of multivariate polynomials and its applications, J. H. Kim, and V. H. Vu, Combinatorica, Vol. 20, No. 3, pp. 417-434 (2000).

[5]. The lower tail: Poisson approximation revisited, S. Janson, and L. Warnke, Random Structures and Algorithms, Vol. 48, No. 2, pp. 219-246 (2014).

2019年1月19日土曜日

マトロイドの基の数え上げの決定的多項式時間近似アルゴリズム

$\mathcal{M} = (E,\mathcal{B})$ をマトロイドとします. ここで $E$ は台集合で$|E|=n$を満たし, $\mathcal{B}$ は基の全体とします. マトロイドの独立性オラクルが与えられたとき, $|\mathcal{B}|$ を求めるという問題を考えます.

マトロイドの数え上げは例えばグラフの全域木の総数やグラフのreliability (分配関数みたいなもの)の計算を求める問題を含んでおり, かなり多くの研究結果があります. 今回の記事では

Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids

という論文の内容について, 簡略に紹介したいと思います. ここで載せたリンクはarXivのものですが, この論文はFOCS 2018に採択されています[1]. 論文そのものはlog-concave polynomialという凄い道具について解析をしており, その一つの応用としてマトロイドの数え上げ近似をするという内容なのですが, 凄い道具の解析は凄い難しく私も咀嚼しきれていないため, 本記事では凄い道具をどのように使って数え上げ近似をするのかについて焦点を絞ります.

論文の概要: log-concave polynomialに関する理論を築いた. その帰結として, ランク $r$ に対して, 独立性オラクルの下でマトロイドの基の総数の$2^{O(r)}$-近似を出力する多項式時間決定的アルゴリズムを与えた. 二つのマトロイドの共通基の個数も同様の近似比のアルゴリズムを与えた. 近似解はマトロイドの基多面体上のある最適化問題を解くことによって得られる.


0. マトロイドの基の数え上げについて



マトロイドの基の数え上げは割と長く研究されていて, これまでは Balanced matroid と呼ばれるクラスのマトロイドに対してはMCMCに基づく多項式時間乱択近似アルゴリズムが知られていました. この辺の話題はNIPS2018のチュートリアルでも関連した話題が取り扱われており, 注目の高さが伺えます.

グラフの全域木の総数は行列木定理により簡単に数えることが出来ます. ではこれを拡張してマトロイドの基は数えられるのでしょうか?

結論から言うとマトロイドの基の数え上げはとても難しいと信じられています. 具体的に言うとバイナリマトロイドの基の数え上げは#P-困難であることが知られています. 従って方向性としては近似アルゴリズムを考えるのが自然です. しかし近似率にも下界が知られており, 独立性オラクルモデルを多項式回呼び出すどんな決定的アルゴリズムも近似比は (P≠NPとは独立に) $2^{\Omega(n/(\log n)^2)}$になることが知られています [2]. この結果の系として, ランク $r\gg\log n$であれば近似比の下界

$2^{\Omega(r/(\log n)^2)}$          ...(1)

が導出されます.

冒頭で述べた通り, balanced matroidと呼ばれるクラスのマトロイドに対してはMCMCに基づく近似アルゴリズムが知られています[3]. 用語を知っている人向けに言うと, このアルゴリズムは
Balanced matroid ならば $\mathcal{M}$ とそのいかなるマイナーに対してもnegative correlationが成り立つので, base exchange graph上のランダムウォークにより基の(近似的な)一様サンプリングが可能になる. そこで Jerrum, Valiand and Vaziraniによる有名な結果 (サンプリングと数え上げ近似の関係) を使うと基の数え上げの近似が出来る.

という流れになっています. 噛み砕いて言うとbalanced matroidだと base exchange graph ($\mathcal{B}$が頂点集合で, 基交換公理によって行き来できる基同士を辺で結んだ巨大なグラフ) がエクスパンダーになっていて定常分布(ここでは一様分布)に早く収束し, 基の一様サンプリングが出来ます. そして実は一様サンプリングが出来れば数え上げで良い近似が出来るという結果が元からあるのでそれを使って数え上げの近似を行う, という流れです. 一般のマトロイドに対して base exchange graph がエクスパンダーかどうかはMihail-Vazirani 予想と呼ばれ, 長年未解決でしたが, 近年解決されたそうです (2019年1月時点ではarXiv上ですが).

重要な用語の定義を述べていきます. サイズ $n$ の台集合$E$上の集合族 $\mathcal{S}$ 及び $\mathcal{S}$上の確率測度 $\mu$ に対して

$g_\mu (x_1,\ldots,x_n) := \sum_{F\in \mathcal{S}} \mu(F)\prod_{e\in F} x_e$

という関数を定めます. この関数を $\mu$ の generating polynomial と呼びます. 以下では特に$\mathcal{S}$に属する任意の集合がサイズ$r$であるような場合のみを考えます (例えばマトロイドの基族). これまで知られている結果として, この関数が $\mathrm{Im}(x_i)>0$ for every $i=1,\ldots,n$ なる任意の点 $\mathbf{x}=(x_1,\ldots,x_n)$に対して $g(\mathbf{x})\neq 0$ を満たす (この性質を real stable と呼びます) ならば, $\mu$に対して自然に定義される$\mathcal{S}$上のランダムウォークは定常分布$\mu$に収束するというのがあります. これによって数え上げの近似っぽいことが出来ます.
マトロイドの基上の一様分布に対するgenerating polynomialがreal stableであればそのマトロイドがbalancedであるということが知られています.

ここまでで述べたように, 基の数え上げに対するアルゴリズムとしてはMCMCに基づくものが基本形でした (特定のマトロイドに関してはad-hocに数え上げるアルゴリズムは存在する). しかし今回紹介する論文では, 決定的なアルゴリズムで近似比が $2^{O(r)}$ となるものを提案します. これは近似比の下界(1)と比較すると右肩にちょっとだけギャップがありますが, とても面白いアルゴリズムです.


1. エントロピーを用いた$|\mathcal{B}|$の近似


情報理論や物理学ではエントロピーという概念がよく知られています. ここでは, 基族上の確率測度 $\mu:\mathcal{B}\to\mathbb{R}_{\geq 0}$ に対して

$H(\mu)=\sum_{F\in\mathcal{B}}\mu(B)\log\frac{1}{\mu(B)}$

エントロピーと呼びます. もし$\mu$が$\mathcal{B}$上の一様分布ならば, $H(\mu)=\log|\mathcal{B}|$ が成り立ちます. もしもランク$r$のマトロイドの基族$\mathcal{B}$上の一様分布$\mu$に対し,
$H(\mu)-r \leq \beta \leq H(\mu)$
を満たす $\beta$ が計算できたとすると, $\exp(\beta)$ は $|\mathcal{B}|$ の$2^{O(r)}$-近似になっています. この$\beta$を計算することを考えます.

台集合$E$の要素 $e\in E$ に対し, $\mu_e:=\mu(\{F\in\mathcal{B}:F\ni e\})$ と定めます. つまり$\mu_e$はアイテム$e$を含む確率 (marginal probability) に対応しています. 論文中では次の結果を証明しています:

Theorem 1.
もしも$\mu$の generating polynomial $g_\mu$ が log-concaveならば, そのエントロピー $H(\mu)$ について, $H(\mu)\geq \sum_{e\in E} \mu_e\log\frac{1}{\mu_e}$ が成り立つ.

Theorem 2.
マトロイドの基族$\mathcal{B}$上の一様分布$\mu$に対応する generating polynomial は log-concave である.

また, エントロピーの劣加法性より, 以下の事実が簡単に確認できます:

Proposition 3.
$H(\mu) \leq \sum_{e\in E}\left(\mu_e\log\frac{1}{\mu_e}+(1-\mu_e)\log\frac{1}{1-\mu_e}\right)=\sum_{e\in E}H(\mu_e)$.

ここで, 関数 $f:x\mapsto (1-x)\log\frac{1}{1-x}$ は $0\leq x\leq 1$に対して $f(x)\leq x$が成り立ちます. 従って, ランク$r$のマトロイドの基族$\mathcal{B}$を考え, $x=\mu_e$を代入して$e\in E$について総和をとると,

$\sum_{e\in E}\mu_e\log\frac{1}{1-\mu_e}\leq \sum_{e\in E}\mu_e \leq \sum_{F\in\mathcal{B}}r\cdot \mu(F)=r$

が得られます. ここで Theorem 1 と Proposition 3 を組み合わせると,

$\sum_{e\in E}(1-\mu_e)\log\frac{1}{\mu_e}\geq H(\mu)-r$

となるので, 系として

Corollary 4.

ランク$r$のマトロイドの基族$\mathcal{B}$上の分布$\mu$に対し, その generating polynomial が log-concave ならば,

$H(\mu)\geq \sum_{e\in E}\mu_e\log\frac{1}{\mu_e}\geq H(\mu)-r$

が成り立つ.




2. 提案アルゴリズム



前節の結果より, marginal probability $\mu_e$ を計算出来れば良いのですが, それはそもそも「アイテム$e$を含む基の個数は?」という問題の答えになっているため, 基の数え上げよりも難しそうです. そこで$\mu_e$を計算せずに済む方法を考えます.

マトロイド$M$の基族 $\mathcal{B}$ 上の一様分布 $\mu$ に対して, $n$次元ベクトル $(\mu_e)_{e\in E}=(\mu_1,\ldots,\mu_n)$ を考えると, 基多面体 $\mathcal{P}_M$ に属する点の一つになっていることがわかります. ここで, 基多面体とは, それぞれの基の indicator vector の凸包として定義されます.

$(\mu_1,\ldots,\mu_n) = \frac{1}{|\mathcal{B}|}\sum_{F\in \mathcal{B}} 1_F$

より確かに marginal distribution のなすベクトルは基多面体$\mathcal{P}_M$内の点に含まれています. そこで, 次の最適化問題を考えます:

maximize: $\sum_{i=1}^n H(p_i)$
s.t.
     $(p_1,\ldots,p_n)\in \mathcal{P}_M$.

Proposition 3より, この問題の最適値 $\beta$ は求めたいエントロピー$H(\mu)=\log|\mathcal{B}|$の上界になっています. しかも, 目的関数は$p$について凹関数になっており, マトロイドの独立性オラクルがあれば$\mathcal{P}_M$上で分離オラクルが構成でき, 楕円体法を用いて多項式時間で解くことができます.

次に, 最適解 $p\in\mathcal{P}_M$ を考えます. 実は(論文中で示されているのですが) marginal distributionが$p$となるような$\mathcal{B}$上の分布$\hat{\mu}$で, generating polynomial $g_{\hat{\mu}}$が log-concave となるものが構成出来ます (つまり, $p_e=\hat{\mu}_e$が成り立つ). この$\hat{\mu}$に対して Corollary 4を適用すると,

$H(\hat{\mu})\geq \sum_{e\in E}\hat{\mu}_e\log\frac{1}{\hat{\mu}_e}=\sum_{e\in E}p_e\log\frac{1}{p_e}\geq \sum_{e\in E}H(p_e)-r\geq H(\mu)-r$.

更に, $H(\hat{\mu})\leq H(\mu)$ が成り立つ (一様分布$\mu$がエントロピーを最大化する) ので, 結果として, 最適化問題の最適値$\beta$に対して

$\beta-r \leq H(\mu)=\log|\mathcal{B}|\leq \beta$

が成り立つので, 近似比 $2^{O(r)}$ が成り立ちます.




3. まとめ



アルゴリズムは単純ですが, 近似比の保証において「generating polynomial $g_\mu$ が log-concaveならば〜」というステートメントが多く出ています. ここで紹介した論文の貢献としては log-concave function の解析にあって, 提案アルゴリズムはその応用先の一つでしかありません (とはいっても重要な結果です). 著者たちは更に別の続編とも言うべき論文 (こちらは2019年1月時点ではarXivに上がっているだけですが) で, Mihail-Vazirani 予想を解決しマトロイドのbase の数え上げに対してMCMCに基づく FPRAS を提案しており, 今後も離散の世界における log-concave 性が発展していくことになるかと思います (連続の世界ではlog-concave はすでに注目されていていろんなことが知られています).


[1]. Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids, N. Anari, S. O. Gharan, and C. Vinzant, In Proceedings of the 59th Annual Symposium on Foundations of Computer Science (FOCS) , 2018.

[2]. On the problem of approximating the number of bases of a matroid, Y. Azar, A. Z. Broder, and A. M. Frieze, Information Processing Letters Volume 50, Issue 1, 1994.

[3]. Balanced matroids, T. Feder, and M. Mihail, In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), 1992.



2018年11月15日木曜日

NPで解を「確かめる」のはなぜか?

私が計算量理論を(独学で)勉強しているときにふと「アレ?」と思ったことについて書かせて頂きます.


1. NPの証拠として正解を使って良いのか?



NPは "Nondeterministic Polynomial" の略で, 非決定的なチューリング機械を用いて多項式時間で解ける問題のクラスです. 非決定的なチューリング機械とは, 計算の各ステップにおいて「鋭い直感」が働き, 迷うことなく解を探索するような機械のことです. 少し話が脱線しますが私はこの概念を専門でない人に説明するとき「NPとはある意味で推理小説で, トリックが分かれば犯人がすぐ分かる殺人事件の総称である. 名探偵(非決定的チューリング機械)なら犯行現場を見たら直感が働き証拠やトリックに気づくが, 一般人(決定的チューリング機械)はすぐには解けない. このことはまだちゃんと証明されてなくて, 数学界で最も有名な未解決問題の一つだ」と言っています.

話が逸れましたが, 私がしばらく (電車内で1時間くらい!) 悩んでいた疑問は以下です:

任意の判定問題には Yes または Noの答えがあります. それでは「鋭い直感によって答えを閃き, それを出力する非決定的チューリング機械」を考えることができるので, 任意の判定問題はNPに属するのではないか?

もちろんこれ(任意の判定問題はNP)が正しかったら, NP=coNPとなってしまい大変なことになってしまいますし, そもそも時間階層定理に矛盾する (NP≠NEXP⊆NP) ので嘘です.

SAT問題を考えます. これは, 与えられた論理式が充足可能解を持つかどうかを判定する問題で, 普通は充足可能な割り当てが証拠となります. しかし, 「与えられた論理式が充足可能なら1, そうでないなら0」と定めた1bit を推理してそれをそのまま出力する非決定的チューリング機械を考えることができます. これはNPの定義としてはなぜいけないのでしょうか?

この疑問に対する答えは, 「解が本当に正しいかどうかを非決定的チューリング機械は確かめなければならない」です. 実は私が1時間くらい本当に悩んでいたのはここからなのですが, この「正しいかどうかを確かめなければならない」性質はクラスNPの形式的な定義のどの部分に表れているのでしょうか?

(*) 判定問題 $L\subseteq \{0,1\}^*$ がNPに属するとは, ある決定的チューリング機械 $M$ と多項式 $p,q:\mathbb{N}\to\mathbb{N}$ が存在して, 任意の $x\in \{0,1\}^*$ に対して
・$x\in L$ ならば, ある $w\in\{0,1\}^{p(|x|)}$ が存在して $M(x,w)=1$ in $q(|x|)$ time,
・$x\not\in L$ ならば, 任意の $w\in\{0,1\}^{p(|x|)}$ に対して $M(x,w)=0$ in $q(|x|)$ time.

2. 対話型証明のProverの「無限の計算時間」とは?



IPも判定問題のクラスの一つです. このクラスの問題には登場人物が2人いて, それぞれを Prover と Verifier と呼びます. 2人は一緒にある問題Xを考えていて, Proverは凄く賢いので答えがすぐ分かったので, それをVerifierに伝え, 納得させたいです. 残念ながらVerifierはそこまで賢くはありませんが, 2人はやりとりを何回か行って, 最終的にはVerifierが答えを出力します. これによって高確率で正解を出力できるという問題をクラスIPと呼びます.

例えば推理小説の犯人摘発シーンを思い起こしてください. めちゃくちゃ賢くて事件の全ての事実を推理できてしまう名探偵 (Prover) がいて, それを刑事 (Verifier) に伝えることを考えます. 刑事は名探偵とのやり取りの中で犯人を定め, その人を逮捕します. 刑事が正しい犯人を逮捕できるかどうかが焦点となります. もし名探偵が犯人・トリック・証拠を提示すれば刑事はそれが正しいかどうかを確かめ, 正しい犯人を確実に逮捕することが出来るので推理小説はNPであると同時にIPでもあります. この「確実に」の部分を「60%以上で」に置き換えたものがIPだと言えます.

ここで一つの疑問として
Proverは答えだけをVerifierに伝え, Verifierはそれを信じてそのまま出力する
というプロトコルを考えたとき, 任意の判定問題が解けることになるのではないか?
について考えます.

結論からいうとこの疑問もNPの時の疑問と本質的に同じで, Verifierは解の正当性を確かめなければいけません.

2018年11月10日土曜日

color-codingと脱乱択化

乱択アルゴリズムとは, ランダムネスの力を上手く活用したアルゴリズムのことで, ここでは「必ず多項式時間で終わるが間違った解を出力するかもしれない」というタイプのアルゴリズムを考えます(モンテカルロアルゴリズム).

本記事では, パラメタ化計算量の分野で有名な乱択アルゴリズムとしてcolor coding[4]を紹介し, その「脱乱択化」の方法 (perfect hash family) を紹介します.

1. color coding


1.1. 背景 (k-PATH)


グラフGが与えられたとき, それが長さkのパスを持つかを判定する問題(k-PATH)を考えます. パスは同じ頂点を二度通らないことに注意してください. $k=n-1$ のとき, ハミルトンパスの判定問題を表現するのでこの問題は $k$ を入力としたときはNP完全となります. 一方で $k=O(1)$ としたときは $n^k$ 時間, すなわち多項式時間で解くことが出来ます. それでは, $k=O(\log n)$ の時は多項式時間で解けるでしょうか? $k=\sqrt{n}$ のときはどうでしょうか? 結論から言うと, $k=O(\log n)$ならばk-PATHは多項式時間で解けますが, $k=\omega(\log n)$の場合は(ETHの下で)多項式時間で解けないだろうと予想されています. color codingを使うと, k-PATHを $2^{O(k)}\cdot n^{O(1)}$ 時間で解くことができます. 以下のそのアルゴリズムを紹介していきますが, 同じ内容は吉田 悠一さんによるこちらの記事にも非常に分かりやすく載っているので紹介させていただきます.


1.2. アルゴリズム



1. 与えられたグラフ $G=(V,E)$ の各頂点をランダムに $k+1$ 色で塗ります. つまり, 各頂点に対して$\{1,\ldots,k\}$から一様ランダムに一つの値を選択しその値の色で塗ります.




2. 色付きグラフ $G=(V,E)$ がカラフルな k-path を含むかどうかを判定します. カラフルなk-path とは, 長さkのパスであって各頂点の色が全て異なる (i.e., $k+1$ 種類の色全てを含む) ようなものです. もしカラフルな k-path を含んでいたら, 元のグラフ $G$ は k-path を含むので終了し, そうでなければステップ1に戻ります.


1.3. アルゴリズムの解析


与えられたグラフ $G=(V,E)$ が k-path を含んでいたとして, その頂点を $v_1,\ldots,v_{k+1}$ としましょう. これらの $k+1$ 個の頂点がカラフルになる確率は

$\frac{k!}{k^k} \approx \sqrt{2\pi k} \exp(-k) \leq 3^{-k}$

となります (スターリングの近似を用いました). したがって上述のステップ1-2を $9^k$回繰り返したとき, パス$(v_1,\ldots,v_{k+1})$が毎回カラフルにならない確率は

$(1-3^{-k})^{9^k} \leq \exp(-3^{-k}\cdot 3^{2k}) = \exp(-3^k)$

となり, 非常に小さくなります (ここでは $1+x\leq \mathrm{e}^x$を用いました). つまり非常に高確率で, $9^k=2^{O(k)}$回の繰り返しの中で一回は k-path はカラフルになり, ステップ2で検出されるので高確率でk-PATHを解くことができることになります.


1.4. カラフルなk-パスの検出


動的計画法を使ってカラフルなk-パスの検出を $O(2^k\cdot n^3)$ 時間で解くことが出来ます. 二頂点$u,v\in V$および色の集合$S\subseteq \{1,\ldots,k+1\}$に対して配列として

$\mathrm{T}[u][v][S]:=$頂点$u$から$v$への, $S$-カラフルなパスが存在すればtrue, そうでなければfalse.

と定めます. ここで $S$-カラフルなパスとは, $|S|$個の頂点からなるカラフルなパスで, 各$c\in S$に対して色$c$で塗られた頂点を一個だけ含むようなものです (下図参照).



色つきグラフ$G$において$N(v)$で頂点$v$の隣接点の集合を表し, $\chi(v)\in \{1,\ldots,k+1\}$で$v$の塗られた色を表すこととします.
すると, $\mathrm{T}[u][v][S]$に対して以下の漸化式が成り立ちます.

$\mathrm{T}[u][v][S]=\bigvee_{w\in N(v)}\mathrm{T}[u][w][S-\{\chi(v)\}]$.

basic caseとして $\mathrm{T}[v][v][\{\chi(v)\}]=\mathrm{true}$ と定めます. また, 自明ですが$\{\chi(u),\chi(v)\}\not\subseteq S$ならばT[u][v][S]=falseです. これにより, カラフルk-パスの判定は$O(2^kn^3)$時間で解けるので, アルゴリズム全体では$9^k\cdot n^3=2^{O(n)}\cdot n^{O(1)}$時間で解けます ($n$の右肩の値はおそらく$2$になると思いますが, 大雑把に見積もっても高々$3$なのは明らかなので今回はそう記しました).


1.5. その他の問題への応用



k-PATH以外にもk-CYCLE (長さkの閉路の検出問題) といった問題も color coding を応用したアルゴリズムによって $2^{O(k)}\cdot n^{O(1)}$時間で解くことができます. 一般に, 入力で与えられたグラフ$G$が頂点数$k$の別のグラフ$H$を含むかどうかは 全探索により$O(n^{k+O(1)})$時間で解けますが, color codingを使うと $2^{O(k)}\cdot n^{O(\mathrm{tw})}$ 時間で解くことが出来ます (twは$H$の木幅です). したがってtwが定数ならば$2^{O(k)}\cdot n^{O(1)}$時間で解けます.


1.6. k-PATHに対するより早いアルゴリズム (advanced topic)



P≠NP予想より強いETHという予想を仮定すると, k-PATH問題は$2^{o(k)}\cdot n^{O(1)}$時間では解けないことが知られています[1]. 今回紹介したcolor coding では$9^k\cdot n^3$時間でしたが, 解析をちゃんとやると $O(\mathrm{e}^kn^3\log n)$時間でwith high probability (i.e., 適当な定数$\epsilon>0$に対し確率 $\geq 1-n^{-\epsilon}$) で正解するアルゴリズムになるはずです. では, 例えば$2.3^k\cdot n^{O(1)}$時間で解けるのでしょうか?

結論から言うと, $2^{k}\cdot n^{O(1)}$時間の乱択アルゴリズムが存在します[2]. このアルゴリズムは
1. 「グラフがk-pathを含まない iff Pは恒等的に0」となる多項式Pを構成する (但しガロア体$\mathrm{GF}(2^{\lceil 4k \rceil})$上の多項式).
2. Schwartz-Zippelの補題を用いてPが恒等的に0かどうかを乱択で判定する (その際に包除原理を用いる).
という流れです. Schwartz-Zippelの補題については相馬 輔 さんによる こちらのページで証明も含めて紹介されています. 更に, 現在では$2^{0.75k}\cdot n^{O(1)}$ 時間アルゴリズムも知られています[3].

この$2^{k}\cdot n^{O(1)}$時間アルゴリズムは様々な道具が登場し非常に面白いものなので, 機会があれば紹介したいと思います.




2. 脱乱択化 (derandomization)



脱乱択化とは文字通り「ランダムネスを排除する」ことです. これまで考えていたアルゴリズムは高確率で正解を計算するものでしたが, 脱乱択化をすると必ず正解を計算するアルゴリズムになります. 計算量理論では, 多項式時間の乱択モンテカルロアルゴリズムで(高確率で)解ける問題のクラス (BPP) が多項式時間で決定的に解ける問題のクラス(P) と等しいかどうかは未解決ですが, 多くの研究者はP=BPPだと信じているようです. P=BPPならば多項式時間乱択アルゴリズムは多項式時間のまま脱乱択化できる, ということになります. ここでは, それに関連したポジティブな結果の一つとして, 先ほど紹介したcolor codingの脱乱択化の方法について紹介します. キーワードはperfect hash familyです.


2.1. color coding is revisited



color codingに基づくアルゴリズムは
(i) グラフを$k$色で塗る.
(ii) カラフルな部分グラフを動的計画法で$2^{O(k)}\cdot n^{O(1)}$時間で見つける.
(iii) 見つけたい部分グラフが(i)でカラフルになる確率が$\geq 2^{-O(k)}$となるので, $2^{O(k)}$回(i)と(ii)を繰り返す.
というものでした.

即ち, 「見つけたい部分グラフが(i)でカラフルになるような塗り分け」をランダムネスを使わず決定的な方法で見つけられたら脱乱択化になります. 


2.2. Perfect hash family



入力で与えられるグラフを$G=(V,E)$とし, その頂点数を$n=|V|$とします. そして塗り分けの集合 $\mathcal{F}$ を考えます. $[m]:=\{1,\ldots,m\}$と表すことにすると, 各要素 $f\in \mathcal{F}$は写像$f:[n]\to [k]$となり, $f(v)$は頂点$v$の色を意味します. つまり$\mathcal{F}$は写像の集合になります. 

定義.
$\mathcal{F}$ が以下の条件(*)を満たすとき, $\mathcal{F}$は $(n,k)$-perfect hash familyと呼びます.
(*) サイズ$k$の任意の部分集合$S\subseteq [n]$ of $|S|=k$ に対して, ある$f\in\mathcal{F}$が存在して, $f(S)=[k]$となる (i.e., 塗り分け$f$の下では$S$はカラフルになる).

$\mathcal{F}$ を $(n,k)$-perfect hash family としましょう. グラフ$G=(V,E)$が入力で与えられたとき, $\mathcal{F}$を構成して全ての$f\in \mathcal{F}$のそれぞれに対してcolor codingの動的計画法のアルゴリズムを使ってカラフルな部分グラフを判定すれば, $T(n,k)+|\mathcal{F}|\cdot 2^{O(k)}\cdot n^{O(1)}$時間で決定的に解くことが出来ます. ここで$T(n,k)$は$\mathcal{F}$の構成にかかる時間です.

$(n,k)$-perfect hash familyについては以下の結果が知られています[4]:

定理.
$(n,k)$-perfect hash family $\mathcal{F}$で
$|\mathcal{F}|\leq \mathrm{e}^kk^{O(\log k)}\log n$
を満たすものを $\mathrm{e}^kk^{O(\log k)}n\log n$ 時間で構成することができる.


これにより, color codingの脱乱択化を$O(\log n)$時間程度のロスでやることが出来ます.


参考文献


[1] D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 84, pp.41–71, 2011.

こちらのサーベイ論文は(題目通り)ETHやSETHの基づいたlower boundとその証明テクニックを幅広く紹介しており, 大変良い論文です. SETHについては以前の記事で紹介しています.

[2] R. Williams, Finding a path of length $k$ in $O^*(2^k)$ time, Journal Information Processing Letters, 109-6, pp. 315-318, 2009.

color codingではk-PATHを$\mathrm{e}^k n^{O(1)}$時間でしたが, こちらの論文はSchwartz-Zippelの補題を用いて$O(2^{k}n^{O(1)})$時間でk-PATHを解くアルゴリズムを提案しています.

[3] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk S. Saurabh, Parameterized Algorithms, Springer International Publishing, 2015.

パラメタ化計算量に関するアルゴリズムを幅広く紹介しています. FPTといった計算量クラス基本的な定義やW-階層といった困難性のクラスやそれらに基づくlower boundについても載っています. 各chapterの後ろには豊富な演習問題とBibliographic notesが載っており, ここには計算量の改善の歴史などが載っています. 誤植もあまりなく, 英語も読みやすいため個人的には非常にオススメの本です.

[4] N. Alon, R. Yuster, U. Zwick, Color-coding, J. ACM, 42-4, pp. 844-856, 1995.

color codingを提案した非常に有名な論文です. 論文中では$k$-CYCLE (長さ$k$の閉路の検出) を用いてcolor codingのアルゴリズムを説明していますが, それのみならず, 木幅が定数のグラフの検出, perfect hash familyを用いた脱乱択化についても書かれています.