SODA21に論文が2本通りました (2/2)

 論文が SODA21 (Symposium on Discrete Algorithms) に 2本採択されました。

・Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

Shuichi Hirahara and Nobutaka Shimizu

arXiv

・How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?

Shuji Kijima, Nobutaka Shimizu, and Takeharu Shiraga

arXiv

の2本です。どちらの論文も非常に面白い内容で、嬉しいことに全ての査読者にかなり褒めて頂きました。

この記事では、前回に引き続き、後者の論文

How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?

の概要をものすごく簡潔に紹介します。

具体的なモデルと結果を述べると少し長くなってしまうので、背景と貢献を簡単に紹介させて頂きます。

実世界に現れるネットワーク上の解析は、そのネットワーク上での様々な現象 (例えば情報拡散など）の振る舞いを知る上で大きな手がかりとなるため非常に重要な研究トピックの一つとなっており、ランダムウォークなどの手法が用いられることが多々あります。

また、実世界に現れるネットワーク (例えばSNSのネットワーク, 化学反応ネットワーク, 携帯電話の基地のセルラネットワークなど) は時間と共にそのグラフ構造が変化します。

この背景を踏まえ、時間とともに変化する動的なネットワーク上でのランダムウォークを理論的に解析するというのが本論文の主題となります。

実は動的なネットワーク上のランダムウォークは幾つか既存研究があるのですが、それらのほとんどは、辺だけが動的に変化するネットワークを対象としています。

というのも、ネットワーク上でランダムウォークを評価する際には、全頂点を訪問するのに必要な時間 (cover time) 、特定の頂点を訪問するのにかかる時間 (hitting time) 、定常分布に収束するまでにかかる時間 (mixing time) などの指標が基本的です。しかし頂点数が動的に変化するようなネットワークに対してはこれらの指標は定義できない（例えば cover time はどうする？）ため、何を解析していいのかがよく分かりませんでした（つまり、ランダムウォークをしている最中にも頂点が増えていくことがあるので、全頂点を訪問するという概念がよく分かりません）。

本論文では、頂点が動的に増え続けるグラフ (growing graph) 上のランダムウォークを評価する指標として、「時刻1からnまでのランダムウォークでカバーされない頂点の個数」を見ることを提案し、様々なタイプのグラフに対してその個数の期待値の上下界を導出しました。

頂点集合が動的に変化するグラフの解析は非常に重要なトピックではあるものの、そのようなグラフ上のランダムウォークはこれまでほとんど解析されていませんでした。でもそのようなグラフ上のランダムウォークの解析は考えるべき課題であり、その需要に応えたという点がこの論文の最大の貢献です。

SODA21に論文が2本通りました (1/2)

論文が SODA21 (Symposium on Discrete Algorithms) に 2本採択されました。

・Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

Shuichi Hirahara and Nobutaka Shimizu

arXiv

・How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?

Shuji Kijima, Nobutaka Shimizu, and Takeharu Shiraga

arXiv

の2本です。どちらの論文も非常に面白い内容で、嬉しいことに全ての査読者にかなり褒めて頂きました。

この記事では、前者の論文

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

の概要をものすごく簡潔に紹介します。

この論文はNIIの平原 秀一さんとの共著です。今年の2月に 冬のLA symposium で発表させていただいた内容を論文としてまとめたものになっています。

この論文は「ランダムグラフの tractability」が主要なテーマです。NP困難な問題は "intractable" であるというイメージを持つ方が多いと思います。しかしながらNP困難であるからといって実用的に解けないというわけではないはずです。なぜならば、その問題がNP困難であるとは、$\mathrm{P}\neq \mathrm{NP}$の下で

任意の多項式時間アルゴリズム $A$ に対し, ある入力の族 $(x_n)_{n\in\mathbb{N}}$ が存在して 全ての$n\in\mathbb{N}$に対し$A(x_n)$は不正解となる

ことを主張しているに過ぎず、つまるところ意地悪な入力 $x_n$ は非常に人工的に構成されたものになるからです。ですので、現実世界にしばしば現れるような入力ではもっと高速に解ける可能性があるはずです！

ということは、問題の時間計算量を、「全ての入力に対し正解する最速のアルゴリズム」ではなく「多くの入力に対して正解する最速のアルゴリズム」で測るという考え方がより実用性に近いと思われます。この考え方を平均計算量といいます。平均計算量のより詳しいフレームワークはこちらを参照してください。

この論文では、「$n^{c+o(1)}$ 時間で解けるとあるグラフ上の問題に対し, (SETHと呼ばれる予想の下で)ランダムグラフ上ですら $n^{c-\epsilon}$ 時間では解けない 」ことを証明しました。具体的には、ランダム二部グラフが入力として与えられたときにそれに含まれる完全二部グラフ $K_{a,b}$ と同型な部分グラフの個数を数え上げる問題を考えます。この問題は愚直にやると $O(n^{a+1})$ 時間で解くことができます (頂点を $a$ 個列挙し、その$a$個全てに隣接している頂点を列挙すれば良い)。また、例えば $a=b=2$ の場合だとこれは四角形の個数をカウントする問題になりますが、これは現状知られている中では $O(n^{\omega})$ 時間が最速です ($\omega <2.373$ は高速行列積の指数). この論文では $K_{a,b}$ 数え上げ問題に対し、

(i). $a\geq 8$ なら $bn^{a+o(1)}$ 時間で解けることを証明

(ii). SETHの下では任意の $\epsilon>0$ に対し, 十分大きな $b=b(a,\epsilon)$ が存在して $K_{a,b}$ の数え上げは$n^{a-\epsilon}$ 時間では解けないことを証明

(iii). ランダム二部グラフ上で $T(n)$ 時間で解けるならば、全ての入力に対し $T(n)\mathrm{polylog}(n)$ 時間で解く乱択アルゴリズムが存在することを証明

しました。

SETH に関しては Hardness in P について紹介しているこちらのページを参照ください。

（ここから先は専門家向けの説明になります）

実はこの論文の最大の貢献は、fine-grained average-case complexity に hardness amplification の枠組みを提供したことにあります。hardness amplification は 平均計算量の世界ではかなりスタンダードなツールなのですが、local list decoding なので uniform な計算モデルで考えようとすると advice が必要になり、fine-grained な世界には実は愚直には適用することができません。しかし、今回のような数え上げの問題のように良い性質を持つ問題ならば適用することができる、というのが最大のウリです。

ICALP20に論文が通りました。

半年くらい前の話になってしまいますが、ICALP2020 (International Colloquium on Automata, Languages and Programming) に論文が通りました。中央大学の白髪 丈晴さんとの共著です。

この論文では以前の論文と同様にグラフ上の合意モデルと呼ばれるものを解析しています。合意モデルでは、各頂点が意見を持った無向連結グラフを考えます。各ラウンドで各頂点は隣接点と通信を行い、予め定められたプロトコルに従い意見を同時に更新します。プロトコルの目的は合意（つまり全頂点が同じ意見を持つ状態）に至ることで、それまでにかかるラウンド数が興味の対象となります。具体的にはpull voting, best-of-two, best-of-three などが非常に有名で、特に分散コンピューティングの文脈でよく研究されています。詳細はリンク先を参照してください。

幾つかの既存結果では best-of-two や best-of-three といった特定のモデルに対してそれぞれアドホックに解析がなされていましたが、本研究の最大の特徴はこれらのモデルを含む幅広い合意モデルのクラス quasi-majority functional voting と呼ばれる合意モデルを提案したことにあります。そして、この広いクラスに属する合意モデルがエキスパンダーグラフ上だと高速 ($O(\log n)$ ラウンド) に合意に至ることを証明しました。

簡単なアイデア

今回は各頂点が二種類$A,B$どちらかの意見を持つケースを考えています。このとき、合意モデルは $2^V$ 上のマルコフ連鎖と見なせます。しかし、完全グラフ上だと $A$の意見を持つ人数にだけ着目すればよくなるので、マルコフ連鎖の状態空間は $\{0,\ldots,|V(G)|\}$ とできるので解析が一気に簡単になります。エキスパンダーグラフ上の合意モデルは、厳密には $2^V$ 上のマルコフ連鎖ですが、実は $\{0,\ldots,|V(G)|\}$上のマルコフ連鎖に「近似」できることを証明しました。この話は best-of-two では既に知られており、Expander Mixing Lemma を用いることで証明できるのですが, この研究ではそれを拡張したいわば "Nonlinear Expander Mixing Lemma" のようなものを証明し、それを利用して幅広い合意モデルの解析に応用しました。

議論をするたびに共著者様がすごく非自明な式変形を涼しい顔で繰り出してこられたのがとても面白かったです（ありがとうございました）

with high probability について

皆さんは with high probability (w.h.p.) という用語をご存知でしょうか。機械学習とかグラフ理論とか色んな文脈で出てきますが文脈に応じて定義が違うのでこれらを整理したいと自分は常々思っています。

例えば、アルゴリズムを扱う文脈 (以後、文脈1と呼ぶ) では、「アルゴリズム $A$ が w.h.p. で $T(n)$ 時間で動く」と言ったときは、ある定数 $c>0$ が存在して

$$\Pr[A \text{ runs in time }T(n)] \geq 1-n^{-c}$$

が成り立つことを意味します。

一方で、ランダムグラフなどの文脈 (以後、文脈2と呼ぶ) では「ランダムに生成されたグラフ $G$ が w.h.p. で性質$\mathcal{P}$ を満たす」と言ったときは、

$$\lim_{n\to \infty} \Pr[G\text{ satisfies }\mathcal{P}] = 1$$

が成り立つことを意味します。

つまり、文脈1の方が漸近のスピードにより厳しい条件を課しています。

自分は両方の文脈に出会うことが多いのでいつも困惑してしまいますが、

文脈2の w.h.p. は asymptotically almost surely (a.a.s.) と言うこともあるようなので、

・文脈1 → w.h.p.

・文脈2 → a.a.s.

と使い分けるようにしています。基本的には両者が同時に出てくることは高確率でないとは思うのですが、自分はレアケースを引いてしまいました...

他にも似たような数学用語として

・almost surely (a.s.)

・almost everywhere (a.e.)

などがありますが、a.e. は測度論で使われる用語、a.s.は確率論で使われる用語で、

・almost surely は 「確率1で」

・almost everywhere は「測度0を除いて」

という意味になるので、基本的には連続の空間で意味をなす用語です。

予想の紹介は止そう

グラフ理論に残されたconjectureを幾つか紹介します。今回の記事は open problem garden を参考にさせて頂き、面白いと感じた予想の中身と簡単なコメントのみを広く浅く紹介させて頂く形になってます。ですのでその予想を思いつくモチベーションとか重要性などは書いていませんので、気になる方は予想の名前で検索して色んな文献を調べてみてください。もし何か間違っている点がありましたらご指摘いただけると幸いです。

1. 5-flow conjecture

登場人物.

・$G=(V,E)$ : ループなしグラフ。ただし多重辺は持ちうる。

・$D$ : $E$の向き付け.

・$\phi:E \to \mathbb{Z}_{\geq 0}$

・$\phi$ が nowhere-zero であるとは、全ての辺 $e\in E$ に対し $\phi(e)\neq 0$ が成り立つことをいう。

・$(D,\phi)$ が $k$-flow であるとは、$\phi$の値域が$\{0,\ldots,k-1\}$であり, 全ての頂点$v\in V$においてキルヒホッフ則を満たすことをいう。つまり、

$$\forall v\in V, \sum_{e\in \delta^{-}(v)} \phi(e) = \sum_{e\in \delta^+ (v)} \phi(e)$$

が成り立つことをいう。ここで$\delta^{-}(v)$ と $\delta^{+}(v)$ は $v$にそれぞれ向き付け$D$において $v$ に入る辺と出る辺の集合である。

Conjecture [Tutte, 1954].

    橋を持たない任意のグラフは nowhere-zero な 5-flow を持つ。

コメント.

・橋を持つグラフならnowhere-zeroなフローはない（橋をどちらの向きにしても流量は保存されないから）。

・5ではなく6なら証明されている [Seymour, 81].

2. Cycle Double Cover Conjecture

登場人物.

・$G=(V,E)$: グラフ.

・閉路の多重集合 $[C_1,\ldots,C_m]$ が $G$の cycle double cover であるとは、$G$の全ての辺がちょうど2個の相異なる $C_i$ と $C_j$ に含まれることをいう。

Conjecture [Szekeres, 73][Seymour, 80].

橋を持たない任意のグラフは cycle double cover を持つ。

コメント.

・cycle double cover が多重集合であることには意味があります。例えば $G$ が単なる閉路の場合は多重集合じゃないと予想の反例になってしまいます。

・$G$が橋を持たない平面グラフなら、面の全体 (外面も含む）が cycle double cover になりますね。

・$G$が橋を持つなら、その橋はいかなる閉路にも含まれないので cycle double cover を持ちません。

・「この予想を証明した」と主張する論文が幾つかarXivにあがっています。

3. The Berge-Furkerson Conjecture

登場人物.

・$G$ : 橋を持たない$3$-正則グラフ.

Conjecture [Fulkerson, 71]

$G$には以下を満たす6個の完全マッチング $M_1,\ldots,M_6$ が存在する:

    全ての辺はそれぞれ$M_1,\ldots,M_6$のうちちょうど2個に含まれる。

コメント.

・$M_1,\ldots,M_6$ は相異なる必要はありません (例えば$M_1=M_2$でもokです)。

・$G$ は必ず完全マッチングを持ちます (cf. ピーターセンの定理)

・$G$ が 3-辺彩色可能なら、それぞれの色を持つ辺集合を$M_1=M_2, M_3=M_4, M_5=M_6$ とすれば構成できます。

・Fulkerson が初めて提示した予想ですが、元々 Berge がこれに似ているちょっと弱い予想をunpublishながら提示していて、それを元に Fulkerson が提示したものらしいです。

・余談ですが、橋を持たない3正則グラフで3-辺彩色可能でないもののうち最小のグラフがピーターセングラフです。ちなみに色んな予想の反例になることで有名なピーターセングラフに対してもBerge-Fulkerson conjectureは成り立ちます。実際、$M_1,\ldots,M_6$ として次が考えられます。

4. Erdős–Gyárfás Conjecture

Conjecture [Erdős, 97].

全ての次数が3以上の任意のグラフは長さが2ベキの閉路を含む.

コメント.

・示したら$100, 反例を見つけたら$50 貰えるらしい。

・3-連結かつ3-正則な平面的グラフでは成り立つ [Heckman, Krakovski, 13].

・次数2の頂点を許すと反例が簡単に構成できます。例えば

・ピーターセングラフは15頂点で長さ4の閉路を持たないのですが、長さ8の閉路を持ちます。

5. Reconstruction Conjecture.

登場人物.

・$G=(V,E)$ : 多重辺を持ちうるグラフ

・$n$頂点グラフ $G$ に対して, $D(G)$ を多重集合 $[H_1,\ldots,H_n]$ であって各 $H_i$ は $G-v_i$ と同型なラベルなしグラフ と定める。ただし $v_i$ は $G$ の $i$番目の頂点。例えば

Conjecture [Kelly, 57][Ulam, 60].

3つ以上の頂点を持つ二つのグラフ $G,H$ が $D(G)=D(H)$ を満たすならば、$G$ と $H$ は同型.

コメント

・要するに、各頂点を削除した時のグラフの形状をみれば元々のグラフ$G$の形状が復元できる、ということを主張しています。

・2頂点だと多重辺を持つグラフ同士が識別できなくなってしまいます。

・$D(G)$ は $G$ の デッキ (deck) と呼ばれます。

・[Kelly, 57] では $G$ が木である場合にreconstruction conjectureが正しいことを証明しています。

6. The Barnette Conjecture

Conjecture [Barnette, 69].

任意の3-連結, 3-正則, 二部な平面的グラフはハミルトン閉路を持つ.

コメント.

・二部という条件は本質で、二部じゃない場合は反例が [Tutte, 46] で見つかっています（二部の条件を外した時のステートメントは元々は[Tait, 1884]が予想していて、Tutteが反例を見つけたということです。詳しくは Tait's Conjecture を参照）。

・3正則平面的グラフがハミルトン閉路を持つかどうかの判定がすでにNP-completeなのでコンピュータによるチェックは大変ですが、66頂点未満のグラフはこの予想が正しいことが知られています [Holton, Manvel, McKay, 85]。100頂点未満のグラフで確認とかしたら学士論文とかになるんじゃないですかね。

グラフ上での確率過程の双対性

前回の記事に引き続き、今回の記事でも双対性について紹介します(?)

双対の概念は最適化の文脈で語られることが多いですが、他にもグラフ理論をはじめとした色んな文脈でも登場します。グラフ理論では平面グラフの双対性、木幅と茨の双対性などが知られています。本記事では確率過程の分野で知られる
・Coalescing Random Walk
・(synchronous) Pull Voting
の双対性を紹介します。

この記事では、$G=(V,E)$ を無向グラフとし、その頂点数を $n=|V|$ で表します。

Coalescing Random Walk (CRW) とはグラフ上の離散時間ランダムウォークの一種です。まず全頂点上にトークンが一つずつ乗っています。そして、各時刻で全てのトークンはそのグラフ上でランダムウォーク（隣接点を一様ランダムに選び、そこにトークンを移動させる）を同時にします。すると同じ頂点に複数のトークンが乗ることがあります。このとき、それらのトークンは合体 (coalesce) して一つのトークンになります。ここまでの流れを1ステップと捉え、トークンが一つになるまでこのステップを繰り返すというのが CRW になります。

CRWのシミュレーション。

赤い頂点にトークンが乗っています。

下の動画はグラフを大きくして高速再生しています。

最後の2,3個のトークンが合体するまでが長いですね。

Pull Voting (PV) ではまず初期状態として、各頂点 $v\in V$ が意見 $o_v\in \{1,\ldots,n\}$ を持ちます。そして各時刻で全ての頂点が同時に隣接点を一つランダムに選びます。その後、自分の持つ意見を、選んだ頂点の持つ意見に同時に更新します。これを全ての頂点が同じ意見になるまで繰り返します。このように、各頂点が合意に至るまで意見を更新し続ける過程を voting process や voting model と呼んだりします。PV は voting process の一つです。以前の記事では別の voting process として Best-of-Two と Best-of-Three を紹介しています。voting process の解析は、ネットワーク上での意見形成 (opinion forming) や、分散コンピューティングにおける合意問題を解決する有効なアプローチとして注目されています。例えば、分散ネットワークシステムでリーダーを決めたいということが多々あります。このときに、PVを行い最終的に合意した色を最初に持っていた頂点をリーダーとすればいいですよね。下の動画はpull votingのシミュレーションです。

　　　  

　　　　 

     

Pull Votingのシミュレーション。色は意見を表します。

最初の数ステップで一気に意見が減ります。

最後の2,3意見が消えるまでが長いですね。

これらの過程を研究する上での興味は、その過程が終わるまでにかかるステップ数です。PVではリーダー選出などを行う際、高速に合意することが望ましいですよね。CRW において全トークンが一つに合体するまでにかかるステップ数を coalescing time と呼び、$T_{\mathrm{coal}}$ と書きます。PVで全頂点が同じ意見に収束するまでにかかる時間を consensus time と呼び、$T_{\mathrm{cons}}$ と書くことにします。

この記事で説明するのは、同じグラフ上での CRW と PV を考えたときに成り立つ

$$T_{\mathrm{cons}} \geq T_{\mathrm{coal}}$$

という不等式です(*)。これの証明は（あとで説明しますが）PV の時間発展を逆再生すると CRW が出てくるという事実を使います。これはある意味で双対になっていて、もう少し一般的な確率過程に対して双対性を使って色んな結果を得たという論文もあります。

(*) 厳密にいうと、$T_{\mathrm{cons}} \leq T_{\mathrm{coal}}$ を満たす coalescing random walk と pull voting のカップリングが存在するという主張です。

まず、以下のグラフ上でのpull voting の時間発展を考えます。説明の都合上、各頂点は自己ループを持つと思ってください（なので、ランダム選択したときに自分自身を選ぶこともありえます）。

図1. グラフ (色は意見を表す)

図2. pull voting の時間発展。矢印は参照関係を表していて、

例えば時刻0で緑は青を選び、オレンジは赤を選びその意見を引っ張る。

最終時刻以外の時刻では全頂点の入次数=1となっています。

次に、図2の各辺の始点と終点を下図のように反転させ、逆再生したものを考えます (隣接した二列の役割が入れ替わった感じです）。

図3. 図2の辺の向きを入れ替え、逆再生した（赤に接続する辺だけ書いた）。

全部の辺をちゃんと書くと初期時刻以外の全頂点の出次数=1になります。

図3を見ると、CRWを再現することができます。図3における$t=0$をCRWの初期状態だと思うと（つまり全頂点にトークンが乗ってる）、トークンの移動を矢印で表現した図と解釈できます。このことは、次の図をみながら考えれば分かると思います。

図4. 一つの頂点に着目したときのPVとCRWの振る舞いの比較.

図4上では、PVのある時刻 $t$ において青頂点がランダム隣人として赤頂点を選択し、その意見を引っ張り時刻 $t+1$ では赤になった様子を表します。図4下では、トークンが乗った赤頂点がランダムに隣人を選択し、そこにトークンを移す様子が図示されています。つまり、「意見を引っ張って赤になった」ことと「トークンを渡して青になった」が逆再生すると全く同じになります。

一方で図3の$t=1$ (右から2番目の列) の一番下の頂点は赤いですが、この解釈でいうとトークンは乗っていません。ですので、「赤頂点＝トークンを持つ頂点」は成り立ちません。しかし、「赤頂点 $\supseteq$ トークンを持つ頂点」は成り立ちます。CRWが終わるまでの時間 $T_{\mathrm{coal}}$ を考えていましたが、これはトークンが一つになるまでの時間でしたので、図2や3から分かるように、PVが合意するまでにかかった時間 $T_{\mathrm{cons}}$ で上から抑えることができます。

厳密な証明ではないですが、このようにPVを逆再生するとCRWが出てくるという性質はとても面白いですよね。

実は$T_{\mathrm{coal}}=T_{\mathrm{cons}}$が成り立つカップリングが構成できます [1].

[1] Petra Berenbrink, Andrea Clementi, Robert Elsässer, and Peter Kling, Ignore or Comply?: On Breaking Symmetry in Consensus, PODC17.

計算量理論におけるuniform/nonuniform

計算量理論は色んな仮定の下で様々な帰結を導出するということをしています。その仮定の中には
・$E\not\subseteq \mathrm{SIZE}[2^{\Omega(n)}]$ (脱乱択化におけるPRG構成の文脈)
・$NP \not \subseteq \mathrm{coNP/poly}$ (FPTのカーネル化の文脈)
・$NEXP \not \subseteq \mathrm{P}/\mathrm{poly}$ (PITの脱乱択化の文脈)
といったものがあります。既存結果の下界はどのような仮定の下で成り立つのかを把握する際にもこれらはどのようなクラスなのかを知っておく必要があります。「/poly」という概念は問題がuniform/nonuniformに解けるということを表します。ここではuniform/nonuniformに解けるとはどういうことかを説明します。

計算量理論には回路計算量というトピックがあります。これはある判定問題に対してそれを解く回路のうち最小サイズがどの程度になるかということを考えます。P$\neq$NP予想は「NP問題のうち多項式時間で解けないものが存在する」ことを意味しますが、同様に NP$\neq$P/poly という予想があります。これは「NP問題のうち多項式サイズの回路で解けないものが存在する」ことを意味します。

それでは、「多項式時間で解ける」ことと「多項式サイズの回路で解ける」ことは異なるのでしょうか？

回路とはどのようなものかを思い出すと、and/or/notゲートとinputゲートからなるDAGであって、$n$変数の回路$C_n$が関数$f:\{0,1\}^n\to\{0,1\}$を計算するというのは

$\forall x\in\{0,1\}^n:C_n(x)=f(x)$

が成り立つことをいいます。判定問題$L$が回路族$\{C_n\}_n$で解けるというのは

$\forall n\in \mathbb{N}$, $C_n$が$L_n$を解く ($L_n$は$L$の入力長$n$への制限)

が成り立つことをいいます。

結論からいうと問題$L$に対してそれが
・uniformに解ける ＝ $L$を解くあるチューリング機械$M$が存在する
・nonuniformに解ける = $L$を解くある回路族$\{C_n\}_n$が存在する
ことをいいます。言い換えると、uniformに解けるといった場合は一つの機械があれば全ての入力に対応できることを意味しており、nonuniformに解けるといった場合は入力長$n$毎に異なる回路を用意できれば解けることを意味します。P/polyは多項式サイズの回路で解ける問題クラスです。

任意のアルゴリズムは少ないオーバーヘッドで回路に変換できる（c.f. Cook-Levinの定理: 3SATのNP困難性の証明) ので、uniformに解けるならばnonuniformで解けます。一方でnonuniformで解けるからといってuniformでも解けるとは限りません。
例えば以下の問題を考えます：

停止性判定問題
入力: $x\in\{0,1\}^*$
出力: Yes iff $x=1^n$ かつ 「$n$を二進表記した文字列が表すチューリング機械が任意の入力に対し有限時間で停止する」

この問題は入力が特別なフォーマットにしたものと捉えることができますが本質的には停止性判定問題を解かなきゃいけないのでuniformには解けません。一方でnonuniformに解くことはできます。回路$\{C_n\}_n$を各$n$ に対し、$x=1^n$ かつ「$n$を二進表記した文字列が表すチューリング機械が任意の入力に対し有限時間で停止する」ような $n$ ならば $C_n(x)=x_1\land x_2\land \cdots \land x_n$ とし, そうでないならば恒等的に0 (例えば $C_n(x)=x_1\land \overline {x_1}$) とすれば、実際に正しい答えを出力しています。

少しいじわるな例だったかもしれませんが、nonuniformに解けるといったときには $n$毎に回路 $C_n$ は外から用意されているから $n$ に問題の本質的な情報を埋め込まれたようなフォーマットの問題に対してはnonuniform と uniform の間にギャップが誕生してしまいます。

一方で、nonuniformに解けるかつ解く回路が構成できるならばuniformに解けます。

木分解は茨の道

0. 概要

以前の記事に紹介したグラフマイナー定理の証明において非常に重要な役割を担うのが木分解 (tree decomposition) という概念です.

木分解に関しては, 色んなサイト (例えばここ) やグラフ理論の本で取り上げられているので, 本記事では木幅の下界の示し方を紹介します. 具体的には, 木幅は minmax の形で定式化できるのですが, その双対となる茨数を maxmin の形で導入し, 強双対性が成り立つことを紹介します.

(＊): 個人的にはtree decompositionのことを「木っぽく」分解するという気持ちから樹状分解と心の中で呼んでいるのですが, ほとんどの方は木分解と呼んでいるのでそれに倣います.

1. 準備

1.1. グラフの定義

グラフ $G=(V,E)$ は無向とし, $E\subseteq \binom{V}{2}$ とする. $G$の頂点集合と辺集合をそれぞれ $V(G)$, $E(G)$ で表す. グラフ $H$ が $G$ の部分グラフであるとは, $V(H)\subseteq V(G)$ かつ $E(H)\subseteq V(G)$ が成り立つことをいう.

1.2 木分解・木幅の定義

グラフ $G$ に対し, 次の性質を満たす組 $(T, \mathcal{V})$ を $G$の木分解と言います.
まず $T$ は木で, $\mathcal{V}=(V_t)_{t \in V(T)}$ は, $T$の頂点 $t$ で添え字付けられた$G$の部分頂点集合族です. そして

     1. $\bigcup_{t \in T} V_t = V(G)$.
     2. $G$ の各辺 $e=\{x, y\}$ に対し, $\{x,y\}\subseteq V_t$ なる $t\in T$が存在する.
     3. 任意の頂点 $v \in V(G)$ に対して, $T$の頂点部分集合 $\{t\in V(T):V_t\ni v\}$ が誘導する $T$ の部分グラフは連結である.

 具体例などはこのページにあるので, ご覧ください. 木分解の役立つ性質として, 以下が知られています:

Proposition1.
グラフ $G$ の木分解 $(T,\mathcal{V})$ を任意にとってくる. ある $t\in V(T)$ が存在して, $G-V_t$の各連結成分の頂点数は高々 $|V(G)|/2$となる.

Proposition 1に出てくる $V_t$のことをセパレータと呼んだりします. 木の場合はある頂点を取り除くと残った二つの連結成分のサイズを $n/2$ 以下にすることができますよね？それと同じ気分です. セパレータを使うと分割統治法とかが使えて良いアルゴリズムが設計しやすくなります.

上: 木分解のセパレータ     下:木のセパレータ

定義2 (木幅)
グラフ $G$ の 木幅 $\mathrm{tw}(G)$ は,
$$\mathrm{tw}(G) = \min_{(T,\mathcal{V})}\max_{t\in V(T)} |V_t| - 1.$$

コメント.
木幅の定義式の $\min$ は$G$の全ての木分解をとります. よく知られるように, $G$が木である iff $\mathrm{tw}(G)=1$ となっており, $\mathrm{tw}(G)$ は $G$ の木っぽさを表す尺度になっています. 定義式の最後の -1 は本質的ではなく, 単に「木の木幅は1である」が成り立つようにするために導入されてるのだと思います (個人的には -1 がない方がいろいろと綺麗になるので良いとは思うのですが...).

2. 双対定理

2.1. 茨

定義3 (タッチ).
$G$をグラフとする. 二つの部分集合 $F_1,F_2\subseteq G$ が
・$V(F_1)\cap V(F_2)\neq \emptyset$, もしくは
・ある二つの頂点 $v_1\in V(F_1),\,v_2\in V(F_2)$ が存在して $\{v_1,v_2\}\in E(G)$
であるとき, タッチしているという.

定義4 (茨).
グラフ $G$ の部分グラフの族 $\mathcal{B}=\{B_1,\ldots,B_m\}$ が以下の条件全てを満たすとき, $\mathcal{B}$ を 茨 という:
・各 $B_i$ は 連結グラフである.
・どの $i,j\in\{1,\ldots,m\}$ に対して $B_i$ と $B_j$ はタッチしている.

定義5 (カバー).
グラフ$G$ の部分グラフ族 $\mathcal{B}=\{B_1,\ldots,B_m\}$ を考える. 頂点部分集合 $C$ が $\mathcal{B}$ をカバーしているとは, すべての $i=1,\ldots,m$ に対して $C\cap B_i\neq \emptyset$ を満たすことをいう. この$C$を$\mathcal{B}$のカバー集合とよぶ. $\mathcal{B}$ のオーダーを, $\mathcal{B}$ のカバー集合のうち最小サイズとする.

定義6 (茨数).
グラフ $G$ の茨数 $\mathrm{br}(G)$ を, $G$の茨の中での最大オーダーで定める. すなわち
$$\mathrm{br}(G) = \max_{\mathcal{B}}\min_{C} |C|$$
である ($\mathcal{B}$ は $G$ の茨全体, $C$ は $\mathcal{B}$ のカバー全体を動く).

例 (グリッドグラフ)

$n\times n$ のグリッドグラフ $G$ を考えます. 下図のような頂点部分集合$B_{ij}$を十字集合と呼ぶことにします.

図1. 茨の例

フォーマルな定義は, グリッドグラフ $G$ の頂点集合が $V(G)=\{(i,j):i,j\in [n]\}$ だとすると, $B_{ij} = \{(y,x):y=i \text{ or }x=j\}$ となります. ここで, $\mathcal{B}=\{B_{ij}\}_{i,j}$ は 茨 になっていることがわかると思います. また, 図右のように, 頂点集合 $\{(i,i)\}_{i=1}^n$ はこの $\mathcal{B}$ のカバーになっていることが分かります. つまり, $\mathrm{br}(G)\geq n$ が分かります.

2.1. 双対定理

木幅と茨数に関する以下の双対定理が成り立ちます.

定理8 (強双対性) [Seymour, Thomas, 1993]
任意の連結グラフ $G$ に対し
$$\min_{(T,\mathcal{V})} \max_{t\in V(T)} |V_t| = \max_{\mathcal{B}}\min_{C} |C|$$
すなわち, $\mathrm{br}(G)=\mathrm{tw}(G)+1$.

コメント (NP=coNP ?).
木幅の計算はNP困難であることが知られており, 木幅$\leq k$ かどうかの判定問題は NP完全です. 一方で定理7を見ると木幅$\geq k'$であることの witness として茨を考えれば良いじゃないかという気もしてきます. ということは, 木幅$\leq k$の判定問題は coNP に属す, すなわち NP=coNP の証明になってしまうのではないか？ ということが気になります. 結論からいう茨そのものは指数サイズになりえるため答えはノーです.

定理8の証明はDiestelのグラフ理論の和訳されたものに載っています. 自分はM2の夏に読んだのですが, 少し長くて大変だった記憶があります.

2.2 例 (グリッドグラフ)

先ほど $n\times n$ のグリッドグラフ $G$ を考えていました. オーダー $n$ の茨を構成していたので, $\mathrm{tw}(G)\geq n-1$ が示されたことになります.

実は, $\mathrm{tw}(G)=n$ になります. というのも木分解として

図2. 最適な木分解 (パス分解にもなる)

このように与えることができます (この木分解により, $\mathrm{tw}(G)\leq n$が言える).

一方で, 最適な茨としては

図3. 最適な茨

図1の青を上図のようにちょっと修正したもので与えられます.

3. 結論

オーダーの高い茨が構成できれば, 木幅の下界を示すことができます. これであなたも立派なグラフマイナー研究者ですね!

駆け足で眺める平均計算量の雰囲気

0. 概要

アルゴリズムの研究をしていると「任意の入力に対して正答する高速なアルゴリズムがあるか」を気にしますが、平均計算量では「ランダムに与えられた入力に対して高確率で正答する高速なアルゴリズムがあるか」を気にします。例えばソーシャルネットワークの解析をしようと思ったとき、どんなグラフでも絶対正答する$\Theta(n^{100})$時間アルゴリズムを使っていては計算が終わらないので困ってしまいます。それよりも、ソーシャルネットワークの特性を利用した高速なアルゴリズムを使うべきです。平均計算量では、そのような高速なアルゴリズムがあるかどうかを議論するわけです（もちろん、入力クラスを制限して高速なアルゴリズムを設計するというアプローチもあります）。

この記事では、平均計算量にはどういうテクニックがあるかを、以下の章立てで簡単に紹介します。
1. 導入
2. 分布問題の例
3. フレームワーク
4. 最悪時から平均時への帰着
5. 誤り訂正符号


(＊) 想定読者としてはアルゴリズム・計算量に興味のある学部生レベルを仮定しています（なので、専門家から見ると物足りないものになってしまうと思います）。

1. 導入

計算量理論のブランチの一つに平均計算量 (average-case complexity) という分野があります。読者の多くは「問題XはNP困難である」「問題Yは2近似アルゴリズムがある」「問題ZはFPTに属する」といった論文を読んだり書いたりしたことがあるでしょう。これらの結果は最悪計算量 (worst-case complexity) に関するものです。つまり「任意の入力に対して解くアルゴリズムが存在するかどうか」を焦点にあてています。

一方で平均計算量では、何らかの確率分布にしたがって生成された入力を高確率で解くアルゴリズムを要請します。この研究には0章で述べたものを含め三つの応用があります。

応用1. 実際のインスタンスに対する計算量
応用2. セキュリティ (困難なインスタンスの生成)
応用3. 脱乱択化

応用1については0章でも述べた通りで、容易に想像できると思います。

応用2について述べます。セキュリティの分野で「素因数分解の困難性に基づいた暗号」などについて聞いたことがあると思います。暗号を設計するとき、その復号化は敵対者からすると難しいものでなければなりません。つまり、困難な問題があればそれは暗号理論に応用できる、ということです。ここで「困難」の意味に注意が必要です。実は、最悪計算量の困難性（例えばNP困難性）だとあまり意味がないです。というのも、最悪計算量の困難性は「任意のアルゴリズムに対して意地悪なインスタンスが存在する」ことを主張するからで、そもそもどんなアルゴリズムでも解けないようなインスタンスを設計することは出来ないです。一方平均計算量の困難性は「任意のアルゴリズムに対してうまくいかないような、多項式時間でサンプリングできる入力分布が存在する」といったことを主張するので、困難なインスタンスはただサンプリングするだけで容易に生成することができます。

応用3は話としては少し難しいので分からなくても良いです。実は、平均的に困難な判定問題があったらその問題を使って擬似乱数生成器 (PRG: Pseudo-Random Generator) を構成することができます。このPRGは、$m$ビットの一様ランダム文字列を受け取って $2^{\Omega(m)}$ ビットの「一様ランダムっぽい」文字列を出力するというものです。例えば多項式時間乱択アルゴリズムを考えたとき、そのアルゴリズムで用いられるランダムネスは多項式ビットなので、PRGで生成した $2^{\Omega(m)}=\mathrm{poly}(n)$ ビットのランダム文字列で代用することができます。このとき、$m=O(\log n)$ なので、長さ $m$ のビットを全探索することができます。こうすると多項式時間乱択アルゴリズムを多項式時間決定的アルゴリズムに置き換えることができるので、P=BPPとなるわけです（BPPは多項式時間乱択アルゴリズムで解ける問題のクラス）。

2. 分布問題の例

3.1. 最大マッチング問題

最大マッチング問題（グラフを入力としてうけとり、最大マッチングを出力せよという問題）を考えます。この問題は多項式時間で解くことができます。簡単のため、ここでは辺に重みはないものとします。既存の中で（最悪計算量の意味で）最速なアルゴリズムは $O(|V|\sqrt{|E|})$時間アルゴリズムです [Micali and Vazirani, 1980]。では、ランダムグラフ上ではより高速に解けるのでしょうか。

ランダムグラフとして、Erdős–Rényi ランダムグラフ $G(n,p)$ を考えます。このランダムグラフは $n$ 頂点を持ち、各頂点対が独立に確率 $p$ で接続されたグラフです。$p=p(n)$ は $n$ の関数になることもあり、例えば $p=1/\sqrt{n}$といったものを考えたりします。今回は、疎なグラフを考えたい（密なグラフだと入力長が大きくなるので）ので、$p=O(\log n/n)$ とします。このとき、辺の本数は$\binom{n}{2}p=\Theta(n\log n)$くらいなので、Micali and Vazirani のアルゴリズムを適用すると大体 $n^{1.5}$ 時間になりますね。

実は、[Erdős and Rényi, 1966]は以下の定理を示しています：

定理1.
数列 $(c_n)_{n\in\mathbb{N}}$ に対し、$p=p(n)=(\log n+c_n)/n$ とする. 偶数頂点数のグラフ $G$ が完全マッチングを持つという事象を $\mathcal{M}(G)$ で表す. このとき、以下が成り立つ：
$$\lim_{n\to\infty}\Pr[ \mathcal{M}(G(n,p)) ] = \begin{cases} 0 & \text{if $c_n\to-\infty$},\\ \mathrm{e}^{-\mathrm{e}^{-c}} & \text{if $c_n \to c$},\\ 1 & \text{if $c_n \to \infty$}. \end{cases}$$

ですので、例えば$p>2\log n/n$ なら高確率で最大マッチングのサイズは$n/2$になることが分かります。それでは、最大マッチング自体は簡単に見つかるのでしょうか？この問題はこれまでいろいろと研究されており（意外なことに、かなりの大御所もこのトピックで論文を書いています！）ので、結果だけを簡単にまとめます。

・十分大きい定数 $C$ に対し, $p>C\log n/n$ ならば, $O(n\log n)$ 時間で見つかる [Angluin and Valiant, 1979].

・$p=\Theta(n^{-1})$のとき、$(1-o(1))$-近似線形時間アルゴリズムが存在する [Karp and Sipser, 1981]. このアルゴリズムは、辺集合 $M\leftarrow \emptyset$ から開始し, (I) 次数1の頂点があればその頂点に接続している辺を $M$ に追加, (II) どの頂点も次数2以上になったらランダムに辺を選んで $M$ に追加しその辺の両端点をグラフから削除し、その後 (I) に戻る という二つの操作を可能な限り繰り返すという単純なものです。

・上記のKarp-Sipserのアルゴリズムは, $p=c/n$ かつ $0<c<\mathrm{e}$ ならば実は最大マッチングを出力する [Aronson, Frieze, Pittel, 1998].

・$p>\log n/n$ ならば, 最短交互道をできるだけとってXORをとるよく知られたアルゴリズム (Hopcroft-Karp や Micali-Vazirani) が実は $O(m\log n/\log (np))$ 時間で終わる ($m\approx n^2p/2$ は辺の本数) [Motwani, 1994]. Hopcroft-KarpやMicali-Vaziraniのアルゴリズムでは最短交互道の長さが高々 $\sqrt{n}$ 種類しかないことを示したため最悪計算量が$m\sqrt{n}$になるが, ランダムグラフ上だとエキスパンダー性を持っているので最短交互道の長さが高々 $O(\log n/\log (np))$ になるという性質を利用している.

・上記のMotwaniの結果は、$p>C/n$ ($C$ は 十分大きな定数) でも成り立つ [Bast, Mehlhorn, Schafer, and Tamaki, 2006].

3.2. クリーク問題

最大クリーク問題（グラフを入力として受け取り、最大クリークを出力せよという問題）を考えます。この問題はよく知られるNP困難問題です。ここでは、最大クリークのサイズではなくクリークそのものを出力せよという問題を考えています。この問題はランダムグラフ上で解けるでしょうか？

ランダムグラフとして、Erdős–Rényi ランダムグラフ $G(n,1/2)$ を考えます。このグラフは、$n$ 頂点ラベル付きグラフ全体から一様ランダムにとってきたものと見なすことができるので、理論の人からすると最も自然なランダムグラフになっています。

$G(n,1/2)$ 上では最大クリークのサイズは大体 $2\log n$ になることが知られています。正確には、$\Pr[G(n,1/2)=(2+o(1))\log n]=1-o(1)$ が示せます。これは、この記事で紹介している First-order method と Second-order method を組み合わせることで証明できます。

実は、単純な貪欲法（任意に選んだ一つの頂点から始めて、クリークになるように一つずつ頂点を追加していき、追加できなくなったら出力するアルゴリズム）を用いると高確率でサイズ $(1-o(1))\log n$ のクリークが得られます。つまり貪欲法は 2-近似アルゴリズム となるわけです（最悪計算量の世界では、P$\neq$NPの下では最大クリークは任意の定数$\epsilon>0$に対して $n^{1-\epsilon}$-近似が出来ないことが知られています）。ここで、一つの疑問が生じます。

疑問.
$G(n,1/2)$ を受け取って高確率でサイズ $\geq (1+\epsilon)\log n$ のクリークを出力する多項式時間アルゴリズムは存在するか？ ($\epsilon>0$ は小さい定数)

実はこの問題は、Karpが1976年に提示して以来、未解決です。多くの変種の問題が考えられており、最も有名なものに planted clique と呼ばれる問題があります。

問題 (Planted Clique)
$G\sim G(n,1/2)$ とし、 $V(G)$からランダムに$k$個の頂点を選びそれを $S$ とする. $S$内の全頂点ペアに辺を追加（つまり$S$はサイズ $k$ のクリークになる）して得られるグラフを$H$とする。アルゴリズムはグラフ $H$ を与えられるので、クリークにした頂点集合 $S$ を出力せよ。

$G(n,1/2)$はサイズ $2\log n$ のクリークを持つので、$k\gg 2\log n$ ならば全探索を使えば検出することができます。また、$k=n/2$とかならば入力そのものが半分完全グラフになるので、貪欲法などで簡単に検出できます。実は $k\geq C\sqrt{n\log n}$ ならば、次数の高い順に$k$個の頂点をとってくればそれが正解であるということが証明できます [Kučera, 1995]。 また, $k\geq C\sqrt{n}$ の場合は隣接行列の第二固有ベクトルなどを見ることで多項式時間で解くことができます [Alon, Krivelevich, and Sudakov, 1998]。AKS98の論文はこの業界の中ではとても有名です。

Planted Clique が注目されている理由の一つには、暗号理論への応用が期待できるからです。自分はあまり詳しくはないのですが、サイズ $k$ のクリーク $S$ という秘密にしたい情報を、$G(n,1/2)$ に埋め込むことで隠せるというのが嬉しいのだと思います。

2. フレームワーク

平均計算量の基本的な用語の定義を並べます。

定義2. (分布問題)
分布問題 $(\Pi,\mathcal{D})$ とは, 問題 $\Pi$ と分布列 $\mathcal{D}=(\mathcal{D}_1,\mathcal{D}_2,\ldots)$ の組である。
問題$\Pi$とその入力$x$に対し、$\Pi(x)$でその問題の答えを表す。

コメント.
問題 $\Pi$ は判定問題とは限りません。数え上げ問題や最適化問題も含みます。分布列$\mathcal{D}_n$はサイズ $n$ の入力上の分布です。例えば $G(n,1/2)$などを考えます。また、「大きいクリークを出力せよ」の類の問題の場合、$\Pi(x)$は大きいクリークのなっている頂点部分集合の族だとします。このとき、アルゴリズムは$\Pi(x)$の要素を出力していれば正解したと見なすことにします。

定義3. (分布問題を解くアルゴリズム)
- 決定的アルゴリズム $A$ が以下を満たすとき、$A$は分布問題 $(\Pi,\mathcal{D})$ を成功確率 $\delta$ で解くという：
$$\forall n\in\mathbb{N},\,\,\,\Pr_{x\sim \mathcal{D}_n}\left[A(x)=\Pi(x)\right] \geq \delta.$$
また、このアルゴリズム $A$ のことを特に ヒューリスティクス と呼ぶ。
- 乱択アルゴリズム $B$ が以下を満たすとき、$B$は分布問題 $(\Pi,\mathcal{D})$を成功確率 $\delta$ で解くという：
$$\forall n\in\mathbb{N},\,\,\,\Pr_{x\sim \mathcal{D}_n}\left[\Pr_B\left[B(x)=\Pi(x)\right]\geq 2/3 \right] \geq \delta.$$

コメント.
- ヒューリスティクスという用語は、最悪時計算量のアルゴリズムと区別するときに用いられます。
- 乱択アルゴリズムの定義に出てくる $2/3$ という数字に意味はありません (1/2より真に大きい定数であればなんでも良いです）。というのも、$B$を繰り返して多数決をとるというアルゴリズムを考えればいくらでも大きくできるからです。


平均計算量の世界では、「任意のアルゴリズムをもってしても成功確率が低い」ような問題が難しいとされます。もちろん、成功確率は低ければ低いほど良いです。

4. 最悪時から平均時への帰着

最悪時から平均時への帰着 (worst-case to average-case reduction) について説明します。2章では、ランダムグラフ上ならば最悪計算量よりも高速に解けるというような例をみてきました（planted cliqueのように、平均時でもなお困難であろうと予想されている問題もみました）。この章では、最悪計算量と平均計算量が同等であるような問題の一つとしてパーマネントの計算問題に着目します。

問題 ($\mathrm{Perm}_q$)
$q$を素数とする。入力として $n\times n$ 行列 $A=(a_{ij})\in \mathbb{F}_q$ が与えられるので、$A$のパーマネント
$$\mathrm{perm}(A) := \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i\sigma(i)}$$
を計算せよ。ここで $S_n$ は $\{1,\ldots,n\}$ 上の置換全体の集合である.

$q$が大きいときの $\mathrm{Perm}_q$ は #P困難問題の一つとしてとても有名で、多項式時間では解けないだろうと言われています（$q=2$ならば行列式と同じになるので多項式時間で解けてしまいます）。また、二部グラフの完全マッチングの数え上げ問題を特殊ケースとして含みます。

ここで、$q$を十分大きな素数として、分布問題として $(\mathrm{Perm}_q,\mathcal{D})$ を考えます。ここで $\mathcal{D}=(\mathcal{D}_1,\ldots,)$ において各 $\mathcal{D}_n$ は $\mathbb{F}_q^{n\times n}$ 上の一様ランダムな分布とします（なので各成分が独立に$\mathbb{F}_q$からとってきたときなランダム行列になる）。

定理4.
$q>n^2$を素数とする. $(\mathrm{Perm}_q,\mathcal{D})$ を成功確率 $1-0.1n^{-1}$ で解く 多項式時間ヒューリスティクスが存在するならば、$\mathrm{Perm}$ を解く多項式時間乱択アルゴリズムが存在する。

証明.
$R\in \mathbb{F}_q^{n\times n}$ を$\mathcal{D}_n$からとってきたランダム行列とする。これに対し、多項式 $H:\mathbb{F}_q \to \mathbb{F}_q$ を$H(t)=\mathrm{perm}(A+tR)$ で定める。このとき、$H$は$n$次多項式である。なぜならば、$\mathrm{perm}(A)$ は定義より、各成分 $a_{ij}$ に関する多項式であって全次数が$n$だからである。

$H$ は一変数多項式なので、$H(1),\ldots,H(n+1)$が分かれば多項式補間により各係数が分かり、全ての$t$に対して $H(t)$ が計算できるようになる。そこで、$H(0)=\mathrm{perm}(A)$を計算し出力すれば良い。

つまり、$H(1),\ldots,H(n+1)$を計算すれば良いが、$H(t)=\mathrm{perm}(A+tR)$をみたとき、$R$がランダム行列なので $A+tR$ もランダム行列となっており、その周辺分布は $\mathcal{D}_n$ そのものになっている。したがって $t\neq 0$ ならば $H(t)$は仮定のヒューリスティクスを用いることで計算できる。

このヒューリスティクスの成功確率は $1-0.1n^{-1}$ なので、全ての$i\in\{1,\ldots,n+1\}$に対して成功する確率は、ユニオンバウンドにより$\geq 0.9$となる。

つまり、確率0.9以上で$\mathrm{Perm}$を解く乱択アルゴリズムが得られたが、このアルゴリズムを繰り返して多数決をとることによって確率はいくらでも大きくできる。

（証明終）

コメント.
定理4の証明は [Lipton, 1991] によるものです。ここでの成功確率 $1-0.1/n$ はすごく強いことを要請していますが、これを緩めた研究というのがその後に続いています。[Cai, Pavan, Sivakumar, 1999] はこれを $1/\mathrm{poly}$ にまで下げました。専門用語を使うと、Reed-Muller符号のリスト復号アルゴリズム と Permに対する sumcheck protocol に基づく対話証明を組み合わせることで下げています。

パーマネント以外にも最悪時から平均時への帰着が知られている問題はいくつかあり、最短ベクトル問題 (SVP) や 離散対数問題などでも知られています。これらの問題は、自分自身への帰着にもなっているので、ランダム自己帰着 (random self-reducibility) とも呼ばれており、計算量理論においてとても重要な概念の一つとなっています。

5. 誤り訂正符号

今までは具体的な問題を見てきましたが、ここからは一気に計算量理論っぽくなります。平均計算量の理論では誤り訂正符号が重要なツールとして活躍するので、それについて紹介したいと思います。前章で述べた最悪時から平均時への帰着の話を誤り訂正符号の観点から解釈することが本章の目標です。以後は、特に断らない限り判定問題のみを考えます。以下の約束事をもうけます。

・判定問題は $f:\{0,1\}^*\to\{0,1\}$によって表現される。
・自然数 $n\in\mathbb{N}$に対して $f_n:\{0,1\}^n\to\{0,1\}$を$f$ の $\{0,1\}^n$ への制限とする。また、$f_n$は長さ$2^n$のビット列と同一視する。つまり $f_n\in \{0,1\}^{2^n}$。
・逆に、$M=2^k$の形になっているとき、文字列$h\in \{0,1\}^M$は一つの判定問題 $h:\{0,1\}^k\to\{0,1\}$ とも見なす。
・分布族 $\mathcal{D}=(\mathcal{D}_1,\ldots)$ は一様分布のみを考える。つまり各 $\mathcal{D}_n$は$\{0,1\}^n$上の一様分布とする。

アルゴリズム $A$ に対し、$\mathrm{str}_n(A)\in \{0,1\}^{2^n}$ を、全ての$x\in\{0,1\}^n$ に対して $A(x)$ を計算して横に並べてできる文字列 $(A(x))_{x\in\{0,1\}^n}$としましょう。

これから次の定理を直感的に証明したいと思います。

定理5（informal).
最悪計算量の意味で難しい問題 $f$ から 平均計算量の意味で難しい問題 $g$ を構成できる。

二つの文字列 $a,b\in\{0,1\}^m$ に対し、それらのハミング距離 $d(a,b)$ を
$$d(a,b) := \Pr_{i\in \{1,\ldots,m\}} [a[i]\neq b[i] ]$$
と定めます（よく使われるハミング距離の定義と定数倍しか変わらないので本質的に等価です）。

もし $A$ が $f_n$ を計算するアルゴリズムであるならば、$\mathrm{str}_n(A)$ は 文字列 $f_n\in\{0,1\}^{2^n}$ と一致するはずです。また、$B$ が関数 $g_m$ を成功確率 $\delta$ で計算するヒューリスティクスであるならば、
$$\Pr_{x\in\{0,1\}^m}[B(x)=g_n(x)] \geq \delta$$
より、$\mathrm{str}_n(B)$ と $g_m$ のハミング距離は $1-\delta$ 以下となります。

ここで、誤り訂正符号とは何なのかを説明します（定義はArora & Barak の本に基づきます）。

定義6 (誤り訂正符号）
$\gamma \in [0,1]$に対し、関数 $E:\{0,1\}^n \to \{0,1\}^m$ が以下の条件を満たすとき、$E$を距離$\gamma$ の誤り訂正符号 と呼ぶ：
$$\forall x,y\in \{0,1\}^n,\,\, x\neq y \Rightarrow d(E(x),E(y)) \geq \gamma.$$

誤り訂正符号のイメージ。赤い点が$\{0,1\}^n$を表していて、$E$の像はまばら。

誤り訂正符号はもともと、通信のための技術として研究されていました。送信者がメッセージ $x\in\{0,1\}^n$ を受信者に送ろうとしたとき、そのまま送ってしまうと通信路でノイズが入ってしまい、別の文字列 $\hat{x}\in\{0,1\}^n$ を受信してしまうことがあります。このノイズは、$x$の各ビットが独立に確率$\epsilon$で反転してしまうものだとしましょう。すると$d(x,\hat{x}) \approx \epsilon$ になりますよね。そこで、距離 $2\epsilon$の誤り訂正符号 $E$を使って $y=E(x)$ を受信者に送ります。するとこのメッセージにもノイズがかかるので受信者は $\hat{y}$ を受信します。今、$d(y,\hat{y})\leq \epsilon$ です。一方でどんなメッセージ $x'\neq x$ に対して、$y'=E(x')$ は、誤り訂正符号の性質より $d(y,y')\geq 2\epsilon$ となるので、$d(y',\hat{y})\geq \epsilon$ が成り立ちます。

$y$と$y'$は遠いが, $y$と$\hat{y}$は近いので、$\hat{y}$から$x$を復元できるかも？

ですので（細かい等号とかは無視するとして）、受信した $\hat{y}$ から $x$を復元できる可能性があります。このように、$\hat{y}$から$x$を復元することを復号化と呼びます。

計算量の話に戻ります。解きたい問題を$f$とします。各$n$に対して、$f_n$を計算するのが目標です。

重要なコメント.
「各$n$に対して$f_n$が計算できる」ことと「$f$が解ける」ことは本来は意味が全く異なります。前者は「全ての$n$に対してあるアルゴリズム$A_n$ が存在して $A_n$ は $f_n$ を計算する」という意味ですが、後者は「あるアルゴリズムが存在して全ての$n$に対して$A$は$f_n$を計算する」という意味なので量化子の順番が違いますよね。この違いは計算量理論においてはとても重要で、前者の「解ける」を「nonuniformに解ける」、後者の「解ける」を「uniformに解ける」と言います。uniformの意味で多項式時間アルゴリズムで解ける判定問題の全体をクラスPと呼びますが、nonuniformの意味で多項式時間アルゴリズムで解ける判定問題の全体はクラス P/poly と呼びます。包含関係としては P $\subseteq$ P/poly が明らかに成り立ちますが、一方で P/poly の属するが P に属さない問題が存在するのでこの包含関係は真です。ひとまずこの記事では nonuniform の意味で解けるかどうかを議論します。

$E:\{0,1\}^{2^n} \to \{0,1\}^M$ を距離 $\gamma$ の誤り訂正符号とします ($E$の定義域のビット長に注意してください）。また、$M=2^k$の形で書けるとします。今、$f_n\in\{0,1\}^{2^n}$ は文字列だったので、$E(f_n) \in \{0,1\}^M$ を考えましょう。この文字列は一つの判定問題と見なすことができますね。この問題を $h_k:\{0,1\}^k\to\{0,1\}$ と書くことにしましょう。

$h_k=E(f_n)$ を成功確率 $\geq 1-\gamma/2$ で計算するヒューリスティクス $A$ があると仮定します。このとき、$\mathrm{str}_A(h_k) \in \{0,1\}^M$ は $E(f_n)$ とのハミング距離が $\leq \gamma/2$ となります。すなわち、我々は $E(f_n)$ から距離が近い文字列へのランダムアクセスを手に入れたことになります。ここまでの議論は、誤り訂正符号の説明・画像においては、$y\leftarrow E(f_n)=h_k$、$y'\leftarrow \mathrm{str}_A(h_k)$ と見なしていますね。

ここで、$\mathrm{str}_A(h_k)$を復号してみると、計算したい文字列 $f_n$ が復元できます！これはつまり $f_n$ が計算できるというわけです。

コメント.
実際のアルゴリズムでは $\mathrm{str}_A(h_k) \in \{0,1\}^M$ をメモリに格納したりはしません。$\mathrm{str}_A(h_k)$ へのランダムアクセスを使って $f_n$ へのランダムアクセスを構成しようとしています。このように、符号化したあとの文字列へのランダムアクセスを使って復元したいメッセージへのランダムアクセスを構成することを局所復号 (local decoding) と呼びます。

ここまでの議論では、$h_k$ を平均的に解くアルゴリズムが存在するならば $f_n$ を任意の入力で計算するアルゴリズムが構成できるということを見てきました。ですので、$f_n$が最悪計算量の意味で困難な問題であったならば、$h_k$は平均計算量の意味で困難な問題であることが帰結として得られます。これが最悪時から平均時への帰着というものです。

小さい体上のSchwartz-Zippelの補題

Schwartz-Zippelの補題と呼ばれる有名な補題があります。

補題 (Schwartz-Zippel の補題)
体 $\mathbb{F}_q$ 上の $d$次多項式 $P:\mathbb{F}_q^n \to \mathbb{F}_q$ を考える。$P$が恒等的に$0$でないならば以下が成り立つ.
$$\Pr_{x\sim \mathbb{F}_q^n} \left[ P(x) = 0 \right] \leq \frac{d}{q}.$$
ここで、$x\sim \mathbb{F}_q^n$ は $x$を$\mathbb{F}_q^n$から一様ランダムにとってきたベクトルとします。

この補題の応用例としては、Tutte行列に対して適用することにより無向グラフの完全マッチングの存在性判定が簡単にできる、といったものがあります。計算量理論では、Reed-Muller符号の距離の証明にもそのまま適用できます。

ところで、$q$が小さいとき、補題の不等式は上界としては弱いものになってしまいます。実は、$\mathbb{F}_2$に着目したSchwartz-Zippel の補題の亜種[1]が知られています。この亜種もReed-Muller符号の距離の証明に使われるようです。

補題.
$P:\mathbb{F}_2 \to \mathbb{F}_2$ を$d$次多項式であり、$P\not\equiv 0$ とする（つまりある$x\in\mathbb{F}_2^n$ に対して $P(x)\neq 0$となる）。
このとき、
$$\Pr_{x\sim\mathbb{F}_2^n} \left[P(x)=1\right] \geq 2^{-d}.$$

証明.
任意の$x\in\mathbb{F}_2$に対して $x^2=x$が成り立つ。したがって$P$は各変数に対しては線形である（例えば $P$ の項で $x_1^2x_3$ があったら $x_1x_3$ に置き換えられる）。したがって $P$は
$$P(x_1,\ldots,x_n) = \sum_{S\subseteq [n]; |S|\leq d} a_S \prod_{i\in S} x_i$$
という形で書ける.

$d$に関する帰納法で示す。

- $d=1$のとき、$P(x)=a+bx$ の形で書ける。$b$の全ての成分が $0$ ならば$P(x)\equiv a\neq 0$となるので主張は成り立つ。そうでないならば、例えば$b_1=1$とすると、$P(x_1,\ldots,x_n)=x_1+(b_2\cdots b_n) (x_2\cdots x_n)^{\top}$ となる。このとき、任意の$b_2,\ldots,b_n\in\{0,1\}^{n-1}$に対して$P(x_1,b_2,\ldots,b_n)=x_1+c$ の形で書けるので、$x_1=0$または$x_1=1$のどちらかは$1$となる。したがって $P(b_1,\ldots,b_n)=1$となる$(b_1,\ldots,b_n)\in\{0,1\}^n$は少なくとも$2^{n-1}$個あるので、主張は成り立つ。

- $d\leq k-1$で成り立つと仮定し, $d=k$において主張が成り立つことを示したい。$P\not\equiv 0$より、ある $S\subseteq [n], |S|\leq k$が存在して$a_S=1$である。例えばこれを $S=\{1,\ldots,k\}$としよう。$d=1$の場合と同じように、任意に$b_{k+1},\ldots,b_n \in \{0,1\}$を固定する。$x_i=b_i$を代入して得られた多項式を$Q$とする。つまり $Q(x_1,\ldots,x_k) = P(x_1,\ldots,x_k,b_{k+1},\ldots,b_n)$。今、$\prod_{i=1}^k x_i$ の係数が$1$ であったので、
$$Q(x_1,\ldots,x_k) = \prod_{i=1}^k x_i + R(x_1,\ldots,x_k).$$
の形で書くことができる。ここで $R$ は $k-1$次多項式である。この $R$ に対して帰納法の仮定を適用すると、
$$\Pr_{(x_1,\ldots,x_k)\sim \mathbb{F}_2^k} \left[ R(x_1,\ldots,x_k) = 1 \right] \geq 2^{-k+1}$$
であるため、$R(x_1,\ldots,x_k)=1$を満たす解$(x_1,\ldots,x_k)$は少なくとも二つ存在する。したがってこれらの解の中に、「どれかの$i\in[k]$に対して$x_i=0$」となるような解が有る。この解を$(x^*_1,\ldots,x^*_k)$とし、$Q(x_1^*,\ldots,x^*_k)$を計算すると、$Q(x^*_1,\ldots,x^*_k)=1$となる。$Q(x^*_1,\ldots,x^*_k)=P(x^*_1,\ldots,x^*_k,b_{k+1},\ldots,b_n)$だったので、すなわち
$$\forall (b_{k+1},\ldots,b_n)\in\mathbb{F}_2^{n-k},\, \exists (x^*_1,\ldots,x^*_k)\in\mathbb{F}_2^k, \,P(x^*_1,\ldots,x^*_k,b_{k+1},\ldots,b_n)=1$$
が成り立つため、$P(x_1,\ldots,x_n)=1$の解は少なくとも$2^{n-k}$個は存在する。これは主張が成り立つことを意味する。　（証明終）

応用（部分グラフの個数の偶奇）

クリークにまつわる次の二つの問題を考えます。

$k$-CLIQUE
入力: 無向グラフ$G$
出力: $G$が$k$-クリークを部分グラフとして含むならYES, そうでないならNO.

$k$-CLIQUE-PARITY
入力: 無向グラフ$G$
出力: $G$に部分グラフとして含まれる$k$-クリークの個数の偶奇.

この二つの問題はどちらの方が難しいでしょうか？実は、上記の補題を使うことにより、以下を示すことができます。

定理 ([2])
$k$-CLIQUE-PARITYを解く$T(k,n)$時間アルゴリズムが存在するならば、$k$-CLIQUEを解く$2^{O(k^2)}\cdot T(k,n)$時間乱択アルゴリズムが存在する。

証明.
グラフ$G$の辺集合を$E(G)$と書くことにします。以下の多項式$P:\mathbb{F}_2^{E(G)}\to \mathbb{F}_2$を考えます。
$$P(x) = \sum_{S\in \mathcal{C}_k} \prod_{e\in S} x_e.$$
ただし$\mathcal{C}_k$ は $G$内でクリークをなす辺 $\{e_1,\ldots,e_{\binom{k}{2}}\}\subseteq E(G)$の全体です。

$G$がクリークを含み、$e_1,\ldots,e_{\binom{k}{2}}$がクリークをなすならば、そのindicator vectorを$x$として代入することにより、$P(x)=1$とすることができます。すなわち、$G$がクリークを含む iff $P\not\equiv 0$ が成り立ちます。なので、$P\not\equiv 0$を上記の補題で判定しましょう。

アルゴリズムとして、$x_1,\ldots,x_m\sim\mathbb{F}_2^{E(G)}$をランダムに$m$個サンプリングし、$P(x_1),\ldots,P(x_m)$を計算します。$P$は$\mathbb{F}_2$上の多項式なので、各$P(x_i)$の計算は$k$-クリークの偶奇の計算でできます（なので$T(k,n)$時間でできます）。もしも$P\equiv 0$だったら全ての$i$に対して$P(x_i)=0$となりますが、$P\not\equiv 0$だったら確率$\geq 2^{-O(k^2)}$で$P(x_i)=1$となります。なので、適当な$m=2^{O(k^2)}$に対して
・$G$がクリークを含む → $\Pr[\forall i, P(x_i)=0] \leq (1-2^{-O(k^2)})^m \leq 0.01$,
・$G$がクリークを含まない → $\Pr[\exists i, P(x_i)=1] = 0$.
すなわち、99%の確率で解くことができます。


コメント
クリークに限らずどんな部分グラフでも同じ議論が適用できます。

参考文献
[1] On the degree of boolean functions as real polynomials, Noam Nisan and Mario Szegedy, computational complexity, volume 4, pages 301--313 (1994)
[2] The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs, Enric Boix-Adserà, Matthew Brennan, and Guy Bresler, FOCS19 (2019).