確率論的手法の計算論的な複雑性 (大雑把なサーベイ)

組合せ論や計算量理論ではしばし, 良い性質を持った離散構造の存在性が議論されます. 例えば

• 疎な正則エクスパンダーグラフ
• girthと彩色数が無限に大きくなるグラフ
• ランダム抽出器 (randomness extractor)
• 困難な真理値表 (hard truthtable)
• rigid matrix
• universal transversal sequence
• 大きい素数
• discrepancyの小さな部分彩色
• quasi-random graph
• Lovász local lemma
• 多変数多項式の根

といった離散構造はそれ自体が興味の対象となるだけではなく非常に幅広い応用をもち, 擬似ランダム生成器, 良い性質を持つ誤り訂正符号, 計算量下界の証明, 脱乱択の証明, 近似アルゴリズムの構成, アルゴリズムの近似率の限界(PCP定理)などに用いられます.

しかしながらこれらの存在性の証明の多くはしばし確率論的手法や鳩の巣原理などに基づいた非構成的な手法もしくは非効率的な構成に基づく証明になっています. 実際の応用では(特に擬似ランダムネスの文脈では)しばし効率的(計算量が小さい)かつ決定的(ランダムネスを使わない)な構成が求められます. これを確率論的手法の脱乱択化と呼ぶことにします. 

確率論的手法の脱乱択化は組合せ論と計算量理論が密接に関連しているとても面白いトピックですので, ここでは非常に大雑把にいくつかのトピックを紹介していきます. なお, この辺りの擬似ランダムネスに関するトピックはVadhanの本に詳しいです.

疎なエクスパンダーグラフ (ラマヌジャングラフ)

頂点数$n$の$d$-正則グラフ$G$を考えます (ただし$n\geq 2, d\geq 3$). 隣接行列$A$の固有値を大きい順に並べて$d=\lambda_1\geq \lambda_2 \geq \dots \geq \lambda_n$とします. すると, 

$$\lambda_2 \geq 2\sqrt{d-1} - \frac{2\sqrt{d-1}-1}{\lfloor \mathrm{diam}(G)/2\rfloor}$$

が成り立つことが知られています(Alon-Boppanaの定理). ここで$\mathrm{diam}(G)$はグラフ$G$の直径で, Moore bound (または幅優先探索に基づく議論)により, $\mathrm{diam}(G)=\Omega(\log_{d-1} n)$が成り立ちます. 従って上記のバウンドにより, $d\geq 3$を固定し$n\to\infty$の漸近を考えると$\lambda_2 \geq 2\sqrt{d-1} - O(1/\log n)$となります.

では, このバウンドは(漸近的に)タイトなのでしょうか? 実はこの問いはランダム正則グラフを考えることで簡単に肯定的に解けます. $n$頂点$d$正則グラフ全体の集合から一様ランダムに選んだグラフを$G_{n,d}$と書くと, Friedman(2003)によると, $n\to\infty$の漸近的を考えると, 確率$1-n^{-0.1}$で$G_{n,d}$は

$$\lambda_2 \leq 2\sqrt{d-1} + O\left(\left(\frac{\log\log n}{\log n}\right)^2\right)$$

を満たすことが知られています. なので, 無限に多くの$n$について上記を満たす$n$頂点$d$正則グラフがとれるため, $n\to \infty$の漸近においてAlon-Boppanaの定理のバウンドはほぼタイトであることがわかります. ちなみにFriedman(2003)の定理の別証明を与えたという論文も知られています.

しかしながらこの証明は非構成的であるという点で応用向きではありません. スペクトルグラフ理論では, $\lambda_2 \leq 2\sqrt{d-1}$を満たすグラフをラマヌジャングラフと呼びます. ある$d\geq 3$に対して$d$-正則ラマヌジャングラフの列$(G_i)_{i=1,2,\dots}$であって, $G_i$の頂点数が$i\to\infty$で発散するようなものが陽に構成できるか, という問題を考えます. この問題はLubotzky, Phillips, Sarnak (1988)によって解決され, その後も様々な進展を見ています.

• Lubotzky, Phillips, Sarnak (1988)は$p\equiv 1 \bmod 4$を満たす全ての素数$p$に対して$(p+1)$-正則ラマヌジャングラフの列を代数的に構成する方法を与えました. この構成はいわゆるLPSラマヌジャンなどと呼ばれています.
• Morgenstern (1994)はLPSラマヌジャンを$p$がprime powerの場合に拡張しました.
• 全ての$d\geq 3$に対して$d$正則ラマヌジャングラフは存在するのでしょうか?Friedmanの定理によるとランダム正則グラフは$\lambda_2 \leq 2\sqrt{d-1}+o(1)$を満たすことが知られていますが, 厳密にはラマヌジャングラフであるということを意味しません. このように, $\lambda_2\leq 2\sqrt{d-1}+o(1)$を満たすグラフをnear-Ramanujan graphといいます.
• Marcus, Spielman, Srivastava (2015)は上の問いを解決し, 任意の$d\geq 3$に対して$d$正則二部ラマヌジャン(multi)グラフの無限列の存在性を証明しました. 彼らの証明はinterlacing polynomial methodと呼ばれる手法に基づいており, LPSラマヌジャンなどの代数的なアプローチとは根本的に異なっています.
• すぐ後にCohen(2016)はMarcus, Spielman, Srivastavaの証明を構成的に修正し, $n$頂点ラマヌジャングラフを$\mathrm{poly}(n)$時間で構成するアルゴリズムを与えました.

ランダムネス抽出器

平たく言うとランダムネス抽出器(または単に抽出器)とは, ランダムっぽい文字列を受け取ってランダムな文字列を出力する乱択アルゴリズムです. 入力で与えられる文字列の「ランダムっぽさ」はmin-entropy(以下で定義している)によって測り, 出力文字列のランダムネスは一様ランダムな文字列との統計距離(total variation distance)によって測ります. 一般にdata processing inequalityより, どのような決定的なアルゴリズムを考えても分布のエントロピーを増大させることはできないため, ランダム抽出器は乱択アルゴリズムとしています.

定義1 (min-entropy).

確率変数$X$のmin-entropy $H_\infty(X)$を以下で定める:
$$\begin{align*} H_\infty (X) = \min_{x\in\mathsf{supp}(X)}\log_2\frac{1}{\Pr[X=x]}. \end{align*}$$

通常のShannon entropyは情報量の期待値によって定義されますが, min-entropyでは情報量の最小値を考えます. すなわちmin-entropyの方がworst-caseの情報量を考えていることになります. 二つの確率変数$X,Y$の統計距離を$d_\mathrm{TV}(X,Y)$で表します.

定義2 (ランダムネス抽出器)

以下を満たす関数$\mathrm{Ext}\colon \{0,1\}^m\times\{0,1\}^d\to\{0,1\}^n$を$(k,\epsilon)$-抽出器と呼ぶ: 任意の$H_{\infty}(X)\geq k$を満たす$\{0,1\}^m$上の分布$X$と$\{0,1\}^d$上の一様分布$U_d$に対し, $d_{\mathrm{TV}}\left( \mathrm{Ext}(X,U_d) , U_n \right) \leq \epsilon$.

すなわち, 抽出器とは, $m$ビットのランダムっぽい文字列$X$と$d$ビットの一様ランダムな文字列$U_d$を受け取り, $n$ビットのランダムな文字列を返す関数のことです. 一般に$m,d$は小さい方がよく, $n$は大きい方が良いです. 入力$X$をしばし弱ランダムソースと呼びます.

ランダムな関数を考えると高確率でランダムネス抽出器になっていることが簡単に示せます. すなわち, 各$\mathrm{Ext}(x,r)$の値を$\{0,1\}^n$上の一様ランダムにとってきたとき, $\mathrm{Ext}(\cdot,\cdot)$が抽出器になっている確率は適切なパラメータの下で$1-o(1)$になることが示せます.

ランダムネス抽出器は以下のように二部グラフによって表現することによって組合せ論的な解釈を与えることができ, そこに組合せ論のテクニックが介入する余地があります.

左側の各頂点は弱ランダムソース$X$の入力に対応しており, 右側の各頂点は$\{0,1\}^n$の元に対応します. 頂点$X$からは$2^d$本の辺が出ており, 各辺には$\{0,1\}^d$の元でラベル付けされています. 頂点$X$からラベル$u\in\{0,1\}^d$の辺を辿った先にある右側の頂点が$\mathrm{Ext}(X,u)$になるようにグラフを構成します.

このように二部グラフを構成すると, 抽出器とは以下の性質を持つ二部グラフ$G=(L,R,E)$であると解釈できます:

左側の頂点集合$L$上のmin-entropy$\ge k$であるような任意の分布に従って頂点$X$を選び, そこから$1$ステップだけランダムウォークを行って得られる右側の頂点を$Y\in R$とする. このとき, $Y$は$R$上一様分布に(統計距離の意味で)近い.

特に, エクスパンダーグラフを考えるとある条件下では抽出器になることが知られています. 抽出器についてのサーベイは, 古い論文ですがNisan(1996)に詳しいです.

エクスパンダーグラフなどの組合わせ論的な道具を使った構成のほかにも, 平均時計算量の道具を使って抽出器を構成するという手法も知られています. Trevisan (2001)は非常に賢いアイデアによって, 多くの擬似ランダム生成器の構成が実は抽出器の構成とみなせるということが示しました. 擬似ランダム生成器(pseudorandom generator; PRG)とは短いランダム文字列を受け取って長いランダム文字列を出力するアルゴリズムです. ただし一般に任意のアルゴリズムはエントロピーを増大しないので, PRGの出力は擬似ランダムであるということが求められます. 詳細は以前の記事をご覧ください. 

例えばNisan-Wigderson generator $G^f_{\mathrm{NW}}\colon \{0,1\}^d\to\{0,1\}^n$は, 計算が非常に困難なBoolean関数$f\colon\{0,1\}^\ell\to\{0,1\}$を使って$d$ビットのランダム文字列$U$(いわゆる乱数シード)を$n$ビットのランダム文字列に変換しています. Trevisan (2001)の抽出器では, 弱ランダムシード$x\in\{0,1\}^m$をまず誤り訂正符号で$2^\ell$ビットの文字列に復号化し, この文字列を真理値表として持つ関数をNisan-Wigderson generatorの構成に用いることによって, 抽出器を構成しています.

解析の大雑把な概要:

もしもTrevisan's extractorの出力値が一様ランダム文字列$U_n$から統計的に離れているならば, Nisan-Wigderson generatorのreconstructionの議論により関数$\mathrm{ECC}(x)\colon\{0,1\}^\ell\to\{0,1\}$からハミング距離$1/2-\epsilon$以下の文字列は短い記述を持つ. さらに$\mathrm{ECC}(x)$に対するリスト復号のアルゴリズムを用いれば, 最終的に弱ランダムシード$x$は短い記述を持つ. これはmin-entropyの仮定に反する.

Rigid Matrix

グラフの剛性とは違う文脈で行列のrigidityと呼ばれる概念があります. 直感的には, $M$がrigidであるというのは, $M$の成分をたくさん書き換えなければ低ランクにできない, ということを意味します. 有限体上の行列$M \in \mathbb{F}_q^{n\times n}$のランクを$\mathrm{rank}(M)$と書き, 二つの行列のハミング距離(異なる成分の個数)を$d_{\mathrm{ham}}(\cdot,\cdot)$で定義します. 

定義3 (matrix rigidity)

行列$M\in\mathbb{F}_q^{n\times n}$と自然数$r\leq n$に対し, $R_M(r)$を
$$\begin{align*} R_M(r) := \min\{|S|\colon \mathrm{rank}(A+S)\leq r\} \end{align*}$$
で定める. ここで, $|S|$は行列$S\in\mathbb{F}_q^{n\times n}$の非ゼロ成分の個数である.

$(n-r)\times (n-r)$首小行列を考えれば任意の行列$M$に対し$R_M(r)\leq (n-r)^2$が簡単に分かります.

各成分を$\mathbb{F}_q$から一様ランダムに選んで得られるランダム行列$M$に対し高確率で$R_M(r)\leq (n-r)^2/\log n$であることが示せます. 実際, ランク$r$以下の行列の個数とハミング距離$\leq s$のボールのサイズを考える数え上げによる議論で示せます.

Rigid matrixの概念はValiant(1977)によって, 線形変換を計算する算術回路のサイズ下界を得るという文脈で導入されました. 大雑把にいうと, Valiant(1977)はrigidな行列に基づく線形変換は超線形サイズの算術回路を要することを証明しており, ランダム行列は高確率でrigidであることを踏まえると, ランダムな線形変換の算術回路複雑性は超線形であることを意味します. この辺りのサーベイについてはLokam(2009)をご覧ください.

線形変換の回路下界自体も重要なトピックで, 例えば高速フーリエ変換は実用的にも重要な線形変換の一つなのでその計算の下界がわかればアルゴリズムの最適性も議論できることになります.

行列のrigidityに関しては次の重要な予想が重要な未解決問題として知られています.

予想 (Valiant, 1977)

ある体$\mathbb{F}_q$, 定数$\delta,\epsilon>0$およびサイズが発散していく陽に構成できる行列の列$(M_n)_{n=1,2,\dots}$が存在して, 十分大きな任意$n\in\mathbb{N}$に対して$R_{M_n}(\epsilon n) \geq n^{1+\delta}$を満たすようにできるか?

現在は$R_M(r)=\Omega\left(\frac{n^2}{r}\log\frac{n}{r}\right)$という下界が知られています(Friedman(1993), Shokrollahi, Spielman, Stemann (1997)).

近年はrigid matrixを計算量の道具を使って(NPオラクルを使って)構成するという手法が開発されました. Alman and Chen (2019)はNPオラクルを用いてrigid matrixを決定的に構成する手法を与えました. この解析は後にrectanglar PCPというアイデアを用いてsimplifyされました (Bhangale, Harsha, Paradise, Tal (2020)). 以下ではrectanglar PCPについてものすごくざっくり説明します.

非決定性機械に対する時間階層定理より, $\mathsf{NTIME}(2^n)\setminus \mathsf{NTIME}(2^n/n)$に属する判定問題$L$が存在します. さらに$\mathsf{NTIME}(2^n)$に対してPCP定理から PCP $\pi$とPCP検証者$V^{\pi}(\cdot)$が得られます. rencangular PCPとはその名の通り, 行列として表現できるPCP $\pi$のことです. ただしPCP検証者はランダムネスを使って行$i$と列$j$を選び, $\pi[i][j]$を見ます. これを定数回繰り返し, 見た証明ビットの内容においじて受理/拒否を決定します. Bhangaleら(2020)はNTIMEで解ける問題に対してある種の性質を満たすrectangular PCPが存在するということを示しています.

PCP定理から, 入力$x$上で元の問題$L$を得くためにはPCP検証者$V^{\pi}(x)$の受理確率を十分な精度で近似できれば良いです. もしrectanglular PCP $\pi$がrigidでないならば, ある低いランク行列$L$にハミング距離の意味で非常に近いはずです. そこで, nondeterministicに$L$の分解$L=R^\top R$をguessします. 実はこの情報を使ってPCP検証者の受理確率を決定的に十分な精度で近似することができます(!!). 実際には受理確率をある行列内に含まれる$1$の個数で表現し, $\pi$の低ランク分解を用いるとその行列もまた低ランク分解できることを示し, 最後に低ランク行列内に含まれる1の個数は高速に数え上げられるという結果(Chan and Williams, 2016)を使い, 最終的に$L$を$\mathsf{NTIME}(2^n/n)$で解けることを主張します. ところがこれは時間階層定理に矛盾するので, rectangular PCP $\pi$はrigidであることが結論づけられます.

その他の話題 (クラスPPAD)

確率論的手法以外にも非構成的な存在性の証明手法はあります. 例えばゲーム理論ではナッシュ均衡の存在性はブラウアーの不動点定理でその存在性が保証されるものの実際にそれを構成しているわけではありません. このような問題を扱うため, 計算量理論ではPPADと呼ばれる計算量クラスが考えられています. ナッシュ均衡の計算やブラウアーの不動点定理における不動点の計算はPPAD完全である, というある種の困難性の結果が知られています (Daskalakis, Goldberg, Papadimitriou, 2009).

まとめ

確率論的手法は興味深い離散構造の存在性を証明できる非常に強力なツールである一方, その離散構造をどのように得るかについては明示的な情報を与えてくれません. それではそれをどのように構成するかに関しては組合せ論や計算量理論で広く研究されており, 驚くほど広い(理論的な)応用を持っています.