分散計算の国際会議DISCに論文が採択されました

中央大学の白髪先生との共著論文が分散計算のトップカンファDISC2019に採択されました。会議は10月の半ばにハンガリーで行われたのですが, 台風19号の影響で私は学会に参加できませんでした (泣). 論文はfullverとproceedings から見れます. 50ページほどの超大作です！証明の気持ち等は少し長くなってしまうので, 結果だけ紹介させていただきたいと思います.

この研究では, グラフ上の合意モデルというものを考えます. 合意モデルでは, 各頂点が意見を持っており, それらが隣人と情報交換をしながら全員が同じ意見になるような状態を目指しています.  ここでは各頂点はAかBどちらかの意見を持つとし, 同期的な合意モデルを考えます. 同期的というのは, 下にある動画のように, 全ての頂点が意見を同時に更新するような合意モデルのことをさします. この研究ではBest-of-twoとBest-of-threeというモデルを考えます. この記事中の図や動画では, 二つの意見を赤色と緑色で表すこととします.

• Best-of-two (以下Bo2) では, 各頂点が隣人を2人ランダムに選び, 自分とその2人の持つ意見で多数決をとり, その意見で更新する.

図1. Bo2の挙動例 (矢印の先 = 選ばれた頂点)

• Best-of-three (以下Bo3) では, 各頂点が隣人を3人ランダムに選び, その3人の持つ意見で多数決をとる.

図2. Bo3の挙動例

 動画1. 完全グラフ $K_{500}$ 上でのBo2のシミュレーション

合意モデルの応用として, 次の設定を考えてみましょう: たくさんの計算ノードを持つシステムにおいては,  外部攻撃などの要因により, 計算途中で一部のノードのデータが破損してしまうことがあります. しかし各ノードは自分の保持するデータが破損しているかどうかは分かりません. そこで, 全頂点の意見の多数決をとることを考えるとき, 合意モデルを使えば良さそうな気がしてきませんか？

Bo2もBo3も, $n$頂点の完全グラフ上では任意の初期状態で $O(\log n)$ ステップで合意 (i.e. 全頂点が同じ意見を持つ状態) に高確率 (確率 $1-n^{-c}$ for some 定数 $c>0$) で至ることが知られています.  また, エキスパンダーグラフ上では, 初期バイアスの仮定 (初期状態で意見に人数差が $\Omega(\sqrt{n\log n})$ あるという仮定) の下では $O(\log n)$ ステップで多数決に合意することが知られています.

この研究では, より複雑な構造をしたグラフ上での合意モデルの挙動解析を究極的な目標と見据え, その第一ステップとして stochastic block model (以下SBM) と呼ばれるランダムグラフ上でBo2とBo3を解析しました. SBMとは, 次で構成されるランダムグラフ $G(2n,p,q)$ のことです: $2n$個の頂点からなるグラフで, 頂点集合が $n$ 個ずつ二つのグループ $V_1,V_2$ に分かれており, 同じグループに属する二頂点を結ぶ辺は確率 $p$ で辺を引き, 異なるグループ間では確率 $q$ で辺を引きます. 辺の有無は各頂点ペアで独立に定めます. 仮定として $p>q$ をおきます. つまり, 同じグループ間はより辺が引かれやすいため, $G(n,p,q)$ は下図のようなコミュニティ構造を持つことが分かります.

図3. $G(300,\,0.1,\,0.01)$

$p=q$のとき, $G(n,p,p)$はコミュニティが一つになりますが, $p$が小さすぎなければ, $G(n,p,p)$はエキスパンダーなので既存研究により, 初期バイアスの仮定の下では $O(\log n)$ステップでBo3とBo3ともに合意に至ることが直ぐ言えます.

下図のように, それぞれのコミュニティが違う意見を指示している初期状態からBo2, Bo3をスタートさせるとどうなるでしょうか？

図4. それぞれのコミュニティが違う意見を指示している.

$p=q$だと$G(n,p,q)$は単一コミュニティなのですぐ合意できますが, $p\gg q$だと喧嘩別れしたままの状態が続き, すぐには合意できなさそうですよね. 実際シミュレートしてみるとそうなることが (実験的に) 分かります.

 

動画2. $G(300,\, 0.1,\,0.04)$ 上の Bo2

動画3. $G(300,\,0.1,\,0.01)$上のBo2

私たちの論文では, 次の結果を証明しました.

定理1 (informal).

$G(n,p,q)$ 上の Bo2を考える. ただし $p\geq q>0$ は$n$ に依存しない定数. 

1. $q/p > \sqrt{5}-2$ ならば, 任意の初期状態に対して高確率で $O(\log n)$ ステップで合意.

2. $q/p < \sqrt{5}-2$ ならば, "喧嘩別れ"の初期状態から開始したとき, 高確率で, 合意に至るまで少なくとも指数時間 $2^{\Omega(n)}$ 時間かかる.

定理2 (informal)

$G(n,p,q)$ 上の Bo3 も定理1と同じことが成り立つ. ただし閾値は$\sqrt{5}-2$ではなく $1/7$.

定理1,2では $p\geq q>0$ は定数なので$G(n,p,q)$は非常にdenseなのですが, よりスパースな状況 ($p\geq q=\omega(\log n/n)$ も考えています. スパースな場合は, $q/p>$閾値かつ初期ギャップの仮定 (初期状態における意見の支持人数差が$\epsilon n$ある) の下で$O(\log\log n)$ ステップで合意に至るものの, $q/p<$閾値ならば初期ギャップの仮定の下でも指数時間かかりうる, という結果もしめしています.

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の下でいうことができます.

グラフの直径と支配集合

グラフの頂点$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.

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.

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

グラフ $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.

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

本来, 確率変数は「ランダムな値をとる」ものであり, その挙動を予想することは困難です. しかし「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).

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

$\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.