「入力」と「インスタンス」の使い分け

問題に対するアルゴリズムの計算量を議論する際に「入力」「インスタンス」という言葉が登場する。これらは、アルゴリズムが読み込む文字列という意味では、両者ともに同じ役割を果たすため、特に気にせず同じ意味で用いる人が多いと思う。しかし、実は両者は文脈によっては明確に区別されるべき概念である。

インスタンス（問題例）の概念は計算量理論の言い回しであり、問題に対して具体的な一例を意味する。例えば最短経路問題は問題であるが、具体的なグラフの一つ一つ（を表す文字列）は最短経路問題のインスタンスという。

一方で入力とはアルゴリズムが受け取る文字列である。例えばクラスNPの検証者は、判定問題$L$のインスタンス$x$および、それがYesインスタンスであることを支持する文字列$w$を証拠として受け取る。このとき、$x$と$w$を区切り文字「$,$」を一つ間に入れて連結させて得られる文字列
\[
x , w
\]
を入力と呼ぶ（もしくはチューリング機械において、インスタンスを記述する入力テープと証拠を記述する入力テープを別々に用意しておく設定を考えるならば、組$(x,w)$を入力と定義しても良い）。

また、乱択アルゴリズム（特にモンテカルロ法）の文脈においても同様である。モンテカルロ法とは、計算時間が有限であるものの、出力が誤りうる乱択アルゴリズムである。したがって乱択アルゴリズムを$A(x;r)$のように記述することがある。ここで$x$はインスタンスであり、$r$はランダムシードである。ここでは$;$という記号はインスタンス$x$とランダムシード$r$の役割が根本的に違うため、その区別を明確にするためだけに採用している。このような場合、$x,r$もしくは$(x,r)$がアルゴリズム$A$の入力であり、インスタンス$x$とは異なる文字列になる。

---

なお、余談であるが「乱択アルゴリズム」の計算モデルには二通りの定義がある。ほとんどの場合はどちらを採用しても構わないので、教科書を執筆するでもない限りは特に気にする必要はないのだが、文脈によって便利な方を採用する。

• 一つ目の定義は二つの遷移関数$\delta_0,\delta_1$を持つチューリング機械であり、便宜上ここでは乱択チューリング機械と呼ぶ。通常のチューリング機械は自身の繊維関数$\delta$を繰り返し適用して計算を進めていくのだが、乱択チューリング機械では各時刻において一様ランダムに$\delta_0,\delta_1$のいずれかを選び、それを適用していく。これは、計算の過程で逐次的にランダムネスを取得する計算モデルなので、オンライン型とも呼ぶ（cf. Goldreich本）。
• 二つ目の定義は、決定的チューリング機械であるが、乱択シード$r$を入力の一部として受け取るモデルである。

例えば「表が出るまでコイントスをし続ける」のように、運が悪いと無限に計算が終わらないような状況では前者の計算モデルで表現するのが適切である。一方で使用したランダムネスの大きさ（ランダムシードの長さ）を議論する場合は後者の定義を採用するのが適切である。例えば後者の議論はPCP定理で非常に重要である。

約束問題についてのお約束

 ある学会で約束問題について言及したら、その後に約束問題について知らなかった人が意外と多かったのが印象的だった。学生であれば知らないのも仕方ないと思うのだが、分野が少し離れた教員にも「知らなくて勉強になった」旨のお言葉をいただいた。確かに計算量理論の論文とかを読まないとこの用語に出会う機会があまりなさそうだし、我々のアウトリーチ不足ということなのだろう。そこで布教もかねてここで簡単に解説することにした。この調子だと接頭辞にioがつく計算量クラス（io-Pとか）も解説しなければならない日が来る気がする。

色々調べたが、約束問題の用語はArora-Barak本にも載ってなかった。こういうときは大体Goldreichが何とかしてくれるのでGoldreich本を調べたらSection 2.4.1に載ってた。他にも

• Goldreichの記事（これを読めば大体OK）
• Sudanのlecture note（$\mathsf{pr\text{-}BPP}$-完全な問題の話）
• Ta-Shmaのlecture note（$\mathsf{pr\text{-}NP}\cap\mathsf{pr\text{-}coNP}$に属していて、かつ$\mathsf{NP}$-hardな問題の話）

が参考資料となる（誤り訂正符号で有名な人がこういう講義資料を書いてるのはビックリ！）

まずは復習がてら、判定問題の定義を述べる。この記事ではアルファベットは$\{0,1\}$に固定する。

定義1 (判定問題).

集合 $L\subseteq \{0,1\}^*$ を判定問題と呼ぶ。

要するに判定問題とは、アルゴリズムが与えられる任意の文字列に対してYesまたはNoの答えが定まっている問題である。では、次の問題は判定問題だろうか？

問題2 (ハミルトン閉路問題).

与えられたグラフ $G=(V,E)$ はハミルトン閉路を含むならばYes、そうでなければNoを出力せよ。

ほとんどの文脈では、ここでは与えられる入力が暗にグラフであることを仮定するのが自然である。しかし、一般にアルゴリズム（チューリング機械）は必ずしもグラフと解釈できない文字列が与えられる。そのような場合、上記の問題2の記述だけでは「グラフと解釈できない文字列が与えられた場合の答えをどうするか？」が明示されていないので、問題2だけを見るとこれは判定問題とは言えないのである。

そこで我々は暗に問題２は

問題2' (ハミルトン閉路問題).

与えられた文字列 $x\in\{0,1\}^*$ は、その長さ$|x|$が平方数であり、$n=\sqrt{|x|}$に対して、
\[
A[i][j] = x[n*i+j] \quad \text{(0-index)}
\]
で定まる行列$A\in\{0,1\}^{n\times n}$が対称行列かつ、それを隣接行列としてもつグラフがハミルトン閉路を含むならばYes、それ以外の場合はNoを出力せよ。

のように、「与えられた入力がグラフであり、かつハミルトン閉路を持つものをYesインスタンスとみなし、それ以外をNoとする」ことによってハミルトン閉路問題を判定問題として扱うことができるのである。このようにフォーマルに判定問題として扱うことによって初めて我々はクラス$\mathsf{P}$やクラス$\mathsf{NP}$に属するか否か、また$\mathsf{NP}$-完全かどうかの議論が可能になるのである。

確かに論文を書くときにいちいち問題2'のような書き方をするのは面倒なので、基本的には論文や口頭発表などでは問題2の形で議論していく。判定問題の計算量クラスを議論する際は常に問題2'のように明示的な判定問題を議論していることを念頭に置くと良い。

例えば、グラフに関する二つの問題のNP完全性の証明とかで考えるカープ帰着を考えてみよう。カープ帰着とは形式的には多項式時間で計算でき、答えを保存する関数
\[
f \colon \{0,1\}^* \to \{0,1\}^*
\]
である。我々は一方の問題のインスタンス$x$をもう一方の問題のインスタンス$f(x)$に変換するわけだが、基本的には元のインスタンスは常にグラフであることを想定し、変換後も常にグラフになるような構成を考える。しかしながら判定問題を議論する以上は元のインスタンス$x$が必ずしもグラフとは限らず、そういう場合は問題2'のような定義では元問題の自明なNoインスタンスであるため、$f(x)$は自明なNoインスタンス（$x$そのものにすればグラフでないので自明にNo）を出力するように定義される。定義に従って厳密に証明するならばこのような処理も明示する必要があるのだが、これは帰着の数学的に本質的な部分ではないしほとんどの場合は省略される。省略によって特に不便はないのだが、この辺りのことは頭の片隅に置いておく方が良いと思う。

一方で問題2のように、与えられた入力が常に何らかの構造（例えばグラフ）を持つことを仮定するという枠組みを考えたい場合も多々ある。計算量理論ではこのような問題を約束問題という。形式的には以下のように定義される：

定義3 (約束問題）

約束問題とは、組$(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$である。ここで、$\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}}\subseteq\{0,1\}^*$は、$\Pi_{\mathrm{yes}} \cap \Pi_{\mathrm{no}} = \emptyset$ を満たす。

また、$\Pi_{\mathrm{yes}}\cup \Pi_{\mathrm{no}}$を約束という。

アルゴリズム$A$が約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$を解くとは、任意の入力$x\in\{0,1\}^*$に対して

• $x\in\Pi_{\mathrm{yes}}$ならば$A(x)=1$
  
• $x\in\Pi_{\mathrm{no}}$ならば$A(x)=0$

が成り立つことをいう。

例えば問題2は、その文面を読むと入力がグラフであると約束されているため、形式的には約束問題と呼ぶべき問題なのである。一般に与えられた$x\in\{0,1\}^*$が約束に属するかどうかが簡単に判定できれば、本質的に複雑性に差異は生まれない。例えば問題2と問題2'は、与えられた入力がグラフの隣接行列かどうかは簡単にチェックできるので、問題2を見たときに暗に問題2'とみなして判定問題として扱うことで、「問題2はNP完全である」という主張はすんなりと受け入れられるわけである。

また、約束問題では、与えられたインスタンスが約束に属さない場合は正解は定義されず、そのような入力上ではアルゴリズムはどのような挙動をしても良い（例えば停止する必要すらない）とされる。

約束問題に対しても$\mathsf{P}$や$\mathsf{NP}$の概念が定義でき、$\mathsf{pr}\text{-}\mathsf{P}$や$\mathsf{pr}\text{-}\mathsf{NP}$などと呼ばれる（記法は文献によって色々異なる）。

定義4 (約束問題の計算量クラス）

約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$は、ある多項式時間アルゴリズム$A$が存在して$A$が$\Pi$を解くとき、クラス$\mathsf{pr}\text{-}\mathsf{P}$に属するといい、そのような約束問題全体の集合を$\mathsf{pr}\text{-}\mathsf{P}$と表す。

また、ある定数$c>0$と多項式時間アルゴリズム$V$が存在して、任意の$x\in\{0,1\}^*$に対して

• $x\in \Pi_{\mathrm{yes}}$ならば、ある$y\in\{0,1\}^{|x|^c}$が存在して$V(x,y)=1$
• $x\in \Pi_{\mathrm{no}}$あらば、任意の$y\in\{0,1\}^{|x|^c}$に対して$V(x,y)=0$

を満たすとき、クラス$\mathsf{pr}\text{-}\mathsf{NP}$に属するといい、そのような約束問題全体の集合を$\mathsf{pr}\text{-}\mathsf{NP}$と表す。

また、上記のyes/noを反転させて定義されるクラスをクラス$\mathsf{pr}\text{-}\mathsf{coNP}$という。

約束が全体集合となる（すなわち$\Pi_{\mathrm{yes}}\cup\Pi_{\mathrm{no}}=\{0,1\}^*$を満たす）ときは判定問題のクラス$\mathsf{P},\mathsf{NP}$の定義と合致することがわかるだろう。

カープ帰着やクック帰着（チューリング帰着）についても同様に定義される。クック帰着については、オラクルへのクエリが約束に属さない場合はオラクルは何を出力しても良いように修正している：

定義5 (帰着）

二つの約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$と$\Pi'=(\Pi'_{\mathrm{yes}},\Pi'_{\mathrm{no}})$に対し、$\Pi$が$\Pi'$にカープ帰着できるとは、以下を満たす関数 $f\colon \{0,1\}^*\to\{0,1\}^*$ が存在することをいう：

• $f$を計算する多項式時間アルゴリズムが存在する。
• 任意の$x\in\Pi_{\mathrm{yes}}$に対し、$f(x)\in\Pi'_{\mathrm{yes}}$
• 任意の$x\in\Pi_{\mathrm{no}}$に対し、$f(x)\in\Pi'_{\mathrm{no}}$

同様に、$\Pi$が$\Pi'$にクック帰着できるとは、あるオラクルアルゴリズム$A^f$が存在して、オラクル$f\colon\{0,1\}^*\to\{0,1\}$が
\begin{align*}
&x \in \Pi'_{\mathrm{yes}} \Rightarrow f(x)=1,\\
&x \in \Pi'_{\mathrm{no}} \Rightarrow f(x)=0
\end{align*}
を満たす任意の$f$について、$A^f$は$\Pi$を解くことをいう。

ここでもやはり、アルゴリズム自体は任意の文字列を入力として受け取ることを想定しており、ただしその場合のアルゴリズムの挙動は不問に伏すことになる。細かいことだが、ここでオラクル$f$はアルゴリズムではなく関数として扱うので、例えば「停止性判定問題を解くオラクル」といった言葉が意味を持つことに注意されたい。

このような帰着に対して完全性や困難性といった概念が定義できる。

グラフの例で述べたように、約束を満たすかどうかの判定が簡単ならば両者に本質的な差異は生まれない。一方でこの判定が難しい場合は興味深い現象が発生する。例として、以下の約束問題 $\Pi$ を考えてみよう：

定義6（充足可能性択一問題）

一方が充足可能、もう一方が充足不可能であると約束されている二つの論理式 $\phi_0,\phi_1$ が与えられたとき、どちらが充足可能かを判定せよ。すなわち

\begin{align*}
&\Pi_{\mathrm{yes}} = \{(\phi_0,\phi_1)\colon \phi_0\in\mathrm{SAT}\text{ and }\phi_1 \in \mathrm{UNSAT} \}, \\
&\Pi_{\mathrm{no}} = \{(\phi_0,\phi_1) \colon \phi_0\in\mathrm{UNSAT} \text{ and }\phi_1 \in \mathrm{SAT} \}.
\end{align*}

なお、それぞれの論理式は変数は共有しない独立な二つの論理式である。

通常のSAT問題は$\mathsf{NP}$完全であり、広く信じられている$\mathsf{NP}\ne\mathsf{coNP}$を仮定すれば$\mathrm{SAT}\not\in\mathsf{coNP}$となる。この記事の最後で証明するが、$\mathsf{NP}\cap\mathsf{coNP}$に属していて、かつ$\mathsf{NP}$困難の問題が存在すれば$\mathsf{NP}=\mathsf{coNP}$が成り立つ。

主張7.

充足可能性択一問題は$\mathsf{pr}\text{-}\mathsf{NP}\cap \mathsf{pr}\text{-}\mathsf{coNP}$に属する。さらにこの問題は$\mathsf{NP}$困難である。

「属する」の部分は簡単に確認できる。YesインスタンスだろうがNoインスタンスだろうが、どちらか一方は充足可能であることが約束されているので、そちらの充足割り当てを証拠とすれば、答えがYes/Noに限らず常に証拠を持って来れる。

$\mathsf{NP}$困難性についても、以下のようにすればSATを解くことができる：充足可能性択一問題を解くオラクルを $f$ とする。SATのインスタンス$\phi$に対して（論理式でない場合はNoを出力）

1.  変数を$x_1,\dots,x_n$とする。各$i=1,\dots,n$に対して以下を実行する：
1. 論理式$\phi$に$x_i = b$を代入したものを$\phi_b$とする（$b\in\{0,1\}$）
2. オラクル$f$の入力$(\phi_0,\phi_1)$に対する答えが$1$であったとき、$\phi'=\phi_0$とする。それ以外の場合、$\phi'=\phi_1$とする。
3. $\phi$を$\phi'$に置き換えて次のループにうつる
2. 最終的に得られた$\phi$は全変数に値が代入されているため$0$または$1$である。その値をそのまま出力する。

SATインスタンス$\phi$が充足不可能であったとすると、各$x_i$にどのような値を代入しても最終的に$\phi=0$になるので、確かにオラクルアルゴリズムは$0$を正しく出力する。

一方で$\phi$が充足可能であったとする。このとき、反復で構成される$\phi'$は常に充足可能であることを証明する。そのために途中で考える$(\phi_0,\phi_1)$について場合わけを考える：

• $\phi_0,\phi_1\in\mathrm{SAT}$のとき：$x_i$にどちらを代入しても充足可能になるので$\phi'$も充足可能である。
• $\phi_0\in\mathrm{SAT},\phi_1\in\mathrm{UNSAT}$のとき：このときは$(\phi_0,\phi_1)$は充足可能性択一問題のYesインスタンスなのでオラクルは必ず$1$を返す。したがって$\phi'=\phi_0\in\mathrm{SAT}$となる。逆の場合も同様。

以上より、確かに択一問題が解ければSATも解けることになるので主張は示された。（証明終）

最後に、以下の主張を証明しておく。これによって、約束問題と判定問題のギャップが明確になるだろう：

主張8.

任意の判定問題$L\in\mathsf{NP}\cap\mathsf{coNP}$に対し、$P^L\subseteq \mathsf{NP}\cap\mathsf{coNP}$。

この主張から、もしもNP困難な判定問題$L\in\mathsf{NP}\cap\mathsf{coNP}$が存在するならば、$\mathsf{NP}\subseteq P^{L} \subseteq \mathsf{coNP}$となり、特に$\mathsf{NP}=\mathsf{coNP}$が従う。

主張の証明：

$P^L$は補問題で閉じているので、$P^L\subseteq\mathsf{NP}$を示せば十分である。そこで任意の$L'\in P^L$を固定し、$L'\in\mathsf{NP}$を示す。$L'\in P^L$より、$L'$を解くオラクルアルゴリズム $A^L$ が存在する。$L'$を検証する証拠を以下で構成する。

Yesインスタンス$x$に対し、$A^L(x)=1$となる。このとき以下を全て証拠として持つことにする：

• オラクル$L$へのクエリ $q_1,\dots,q_m\in\{0,1\}^*$ ($A$は多項式時間なので、これらのクエリは多項式長）
• 各クエリ $q_i$ に対するオラクルの返答 $a_i \in \{0,1\}$
• $a_i=1$のとき、$q_i \in L$ であることの証拠 ($L\in \mathsf{NP}$なのでそのような証拠が存在する）
• $a_i = 0$のとき、$q_i\not\in L$であることの証拠（$L \in \mathsf{coNP}$なので、同様にとれる）

すなわち$L'$のNP検証者としては、オラクルアルゴリズム$A^L$を、証拠をオラクルの返答とみなして模倣し、最終的にそれが$1$を出力したら受理するというものを考えればよい。

$x$がYesインスタンスのときは確かに上記の証拠を用意できる。Noインスタンスに対しては$A^L(x)=0$になるので、

• $A^L$を模倣する途中で証拠との整合性がとれなくなり、この時点で検証者は拒否
• もしくは整合性が完全に取れたとすると$A^L(x)=0$になるので検証者は拒否

となる。（証明終）

Håstadのスイッチング補題

回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0$回路 (非有界fan-inをもつ定数段回路のクラス)に対するタイトな下界を証明できます. 証明の本質には決定木が深くなるようなDNFの部分代入は短い長さで記述できる (従ってそのような部分代入の個数は相対的に少ない) というアイデアを使っています.

スイッチング補題は海外の大学に講義資料があり, 本記事もそれらを参考にしました:

• lecture note by O’Donnell … 長いがかなり丁寧.
• lecture note by Jonathan Katz … 証明は短く簡潔. O’Donellの証明の要約
• lecture note by Lovett … 証明はしていないがさまざまな帰結をFourier analysisの視点から紹介

1. 準備

CNF, DNF, 決定木など必要な概念を定義していきます.　ここでは$n$変数の論理関数といえば$\{0,1\}^n \to \{0,1\}$を意味し, true/falseをそれぞれ1/0で表します.

定義1.1 (CNF, DNF).

• 論理変数$\mathrm{x}$に対して, $\mathrm{x}$と$\overline{\mathrm{x}}$をリテラル (literal) と呼ぶ.
• 複数のリテラルを$\lor$で繋げたもの $\ell_1 \lor \dots \lor \ell_w$ を節 (clause) と呼ぶ. 同様に, 複数のリテラルを$\land$で繋げたもの $\ell_1 \land \dots \land \ell_w$ を項 (term) と呼ぶ. このとき, 繋げたリテラルの個数$w$を幅 (width) と呼ぶ.
• 複数の節 $C_1, \dots, C_m$ を $\land$ で繋げた論理式の表現形式を連言標準形 (CNF) と呼ぶ. 同様に, 複数の項 $T_1,\dots,T_m$ を $\lor$ で繋げたものを選言標準形 (DNF) と呼ぶ. この記事ではそれぞれをCNF, DNFと呼ぶことにする.
• 特に, 全ての節 (項) の幅が$w$以下であるCNF (DNF) を$w$-CNF (DNF)という.

ド・モルガンの法則より, CNFの否定をとるとDNFになります. 従って, 本記事ではCNFとDNFはDNFに焦点をあてて説明しますが, 否定をとることによってCNFに変換しても同じことが成り立ちます.

図1. 3-DNFの例

CNFやDNFはあくまでも論理式のフォーマットの一つです. $n$変数の論理式は全部で$2^{2^n}$個あるので, その全てを表現しようとすると$2^n$ビット必要となりますが, 項が$m$個の$w$-DNFは$O(mw\log n)$ビットで表現できるので, $m$と$w$が小さいときのDNFは論理式のコンパクトな表現になっています. 逆に, 任意の論理関数は$2^n$個の項をもつ$n$-DNFで表現できます.

図2. 真理値表からDNFへの変換

定義1.2 (決定木).

次の性質を持つ二分木を決定木 (deceision tree) という:

• 葉には0または1のラベルがついていて, 葉以外の頂点はどれかの変数でラベル付けされている.
• 葉以外の各頂点から子に向かう二本の辺には0または1のラベルがついている.

決定木による計算では, 根から開始して入力に応じて葉に向かって遷移していき, たどり着いた葉のラベルを出力する. 遷移の規則は次のようにして定める: 現在いる頂点のラベルの変数$x_i$に対し $x_i=b \in \{0,1\}$ならばラベル$b$の辺に沿って子に遷移する.

論理関数 $f\colon \{0,1\}^n\to\{0,1\}$と等価な決定木の中での最小の深さを$f$の決定木複雑性と呼び, $\mathsf{DT}(f)$で表す.

図3. 決定木の例.

決定木複雑性が小さい回路は幅の小さいDNFで表現できます.

観察1.3 (決定木$\Rightarrow$DNF).

論理関数$f$が$\mathsf{DT}(f) \le w$を満たすならば, $f$は$w$-DNFで表現できる.

図4. 各1の葉に対し, そこに至るパスに対応する割り当てを1にする項を作る. これらの項をORでつなげればよい.

同様に, 否定を考えることによって, 幅の小さいCNFも構成できます.

任意の$n$-変数の論理関数$f$は全ての変数の割り当てを列挙することによって深さ$n$の決定木で表現できます. これを$f$の自明な決定木と呼ぶことにします. 自明な決定木は深さ$n$の完全平衡二分木です.

2. Håstadのスイッチング補題

Håstadのスイッチング補題は, 幅の小さいDNFの変数をいくつかランダムに選んでランダムに0または1を代入すると決定木複雑性が小さくなるということを主張します. 結果をフォーマルに述べるために, ランダム制限という概念を以下で定義します.

定義2.1 (制限).

パラメータ$n,s\in\mathbb{N}$に対し, $n$変数の$s$-制限 (または部分割り当て) とは関数$\alpha\colon [n] \to \{0,1,\star\}$であって, $s$個の$i\in[n]$に対して$\alpha(i) = \star$を満たすものである. $s$-制限全体の集合を$\mathcal{R}_s$とする (ここでは$n$は固定して考える. $\mathcal{R}$はrestrictionの略). $\mathcal{R}_s$から一様ランダムに選ばれた制限をランダム$s$-制限と呼ぶ.

$s$-制限$\alpha$は部分的に変数に代入を行う操作 ($\alpha(i)=0$ならば$x_i\leftarrow 0$, $\alpha(j)=1$ならば$x_j\leftarrow 1$) として捉える. 変数$x_1,\dots,x_n$をもつ論理関数 $f\colon \{0,1\}^n \to \{0,1\}$ に対してこの部分的な代入操作を行なって得られる$s$変数論理関数を$f|_\alpha$とする.

$s$-制限とは$s$変数関数にするという操作です. ランダム$s$-制限とは, ランダムに$n-s$個の変数を選んで$0$または$1$をランダムに代入するという操作です.

図5. $1$-制限の例.

定理2.2 (スイッチング補題 [Håstad, 1986]).

$w$-DNFで表現される論理関数 $f \colon \{0,1\}^n \to \{0,1\}$ に対するランダム$s$-制限$\alpha$は以下を満たす:
\begin{align*} \Pr_\alpha\left[ \mathsf{DT}(f|_\alpha) > d \right] \le \left(\frac{4w s}{n-s} \right)^d \end{align*}

冒頭にも述べたとおり, Håstadのスイッチング補題とは幅の小さいDNFの変数をランダムにいくつか選んでランダムに代入操作を施すと, 得られる関数は浅い決定木で表現できるという結果です.

応用の一つとしてparity関数のAC0回路下界の証明にあります. AC0回路とは, 定数段でfan-in (各素子の入次数) が非有界なものです. parity関数とは入力の中の$1$の個数の偶奇を出力する関数です. 

図6. AC0回路のイメージ. 途中の$\neg$素子は省略.

スイッチング補題および観察1.3より, ランダムな制約を考えるとDNFをCNFに変換することができます. これをAC0回路の最下段に適用すると, $\lor$と$\land$の切り替えの回数を一つだけ減らせます. これを定数回だけ繰り返すとAC0回路は最終的には定数関数になってしまいます. 一方でparity関数は$s>0$である限り, どのような$s$-制限を考えても定数関数になりません. この差異によって回路下界を証明するという算段です. 詳細は省略します.

3. スイッチング補題の証明

3.1. 証明の方針

$w$-DNF $f$ の$s$-制限$\beta \in \mathcal{R}_s$ が $\mathsf{DT}(f|_\beta)>d$ を満たすとき, $\beta$はbadであると呼びます. badな$s$-制限の集合を$\mathcal{B}$とし, $|\mathcal{B}|$が小さいことを証明していきます. そのために, DNFのbadな制限は簡潔な記述を持つことを証明します.

フォーマルに述べると, サイズの小さいある集合$\Omega$に対して単射$\varphi \colon \mathcal{B} \to \Omega$を構成することで$|\mathcal{B}|\le |\Omega|$を示します. さらに, $|\Omega| \le \left(\frac{10sw}{n}\right)^d\cdot |\mathcal{R}_s|$ となることを示せたとすると, 所望の確率は

\begin{align*} \Pr_\beta\left[ \mathsf{DT}(f|_\beta) > d \right] \le \frac{|\mathcal{B}|}{|\mathcal{R}_s|} \le  \frac{|\Omega|}{|\mathcal{R}_s|} \le \left(\frac{10sw}{n}\right)^d. \end{align*}

となり, 主張を得ます.

3.2. 準備

$w$-DNF $f$の各項が順序づけられており, $f=T_1 \lor T_2 \lor \dots T_m$とします. さらに, 各項$T_i$に含まれるリテラルも変数の番号によるデフォルトの順序があるとします. 例えば$T_1=x_1\lor \overline{x_3} \lor x_5$ならば$x_1,x_3,x_5$という順があります.

badの$s$-制限$\beta$に対して$f|_\beta$もまた$w$-DNFであり, これを

\begin{align*}
f|_\beta = T_{i_1} \lor \dots \lor T_{i_\ell}
\end{align*}
とします. ここで, $\beta$によって$T_i\equiv 1$となる項が存在すると$f|_\beta\equiv 1$となってしまいbadであることに矛盾してしまいます. 同様に「全ての項が0に固定されてしまう」こともありません. 従って上記のような形で$f|_\beta$を表現できます.

図7. canonicalな決定木の構成.

$f|_\beta$の項$T_{i_1},\dots,T_{i_\ell}$の幅がそれぞれ$d_1,\dots,d_\ell$とします. このとき, canonicalな決定木$\mathcal{T}$を以下で定義します: 先頭の項$T_{i_1}$を$d_1$変数の論理関数とみなしたとき, その自明な決定木を$\mathcal{T}_1$とします. $T_{i_1}$は項なので, 充足割り当てはただ一つしか存在しません. 従ってこの決定木$\mathcal{T}_1$はただ一つの$1$の葉を持っています. この唯一の葉を$\mathcal{T}$における$1$の葉とします. 残りの$2^{d_1}-1$個の$0$の葉に対して, これを根として$T_{i_2}, T_{i_3},\dots$の順で同様の操作を続けていきます. ただし, 固定された変数はそれ以降の項でも固定します. 例えば$\mathcal{T}_1$のある葉において$x_1=0$と固定されている場合は, その葉に続けて構成していく$\mathcal{T}_2,\mathcal{T}_3,\dots$においても常に$x_1=0$として扱います. なお, この固定によって途中で$T_{i_j}$の値が0に固定されてしまった場合はそのままスルーして$T_{i_{j+1}}$に移動します. これは, 例えば$T_{i_1},T_{i_2}$での操作によって$x_1$から$x_5$までの変数が全て固定されていたときに$T_{i_3}$に含まれる変数が$x_2,x_3,x_5$であった場合などに起こりえます.

図8. canonicalな決定木上の長いパス$P$.

部分割り当て$\beta$がbadであるため, このように構成されたcanonicalな決定木$\mathcal{T}$の深さは$d$を超えます. 従って根を始点として子に伝っていく長さ$d$のパスが一つ以上存在します. そのようなパスの中で割り当てが辞書順最小のものを$P$とします. ここで, canonicalな決定木はその構成から, 代入される変数の順番は固定長のパスの中ではどのパスを選んでも同じになります (固定の仕方によっては途中で$1$の葉に行き着く可能性もあるので, パス長は固定して考える). 従って長さ$d$のパスが固定する変数はどれも同じ変数を選ぶため, 辞書順最小な割り当てを持つパス$P$が一意に定まります.

このパス$P$が経由する項を順番に$T_{i_1},\dots,T_{i_k}$とします. パス$P$はちょうど$d$個の変数の値を固定するため, 最後の行$T_{i_k}$は部分的に値が固定される可能性があります.

3.3. badな制限のencoding

図9. badな制限の記述

3.2で定義されたパス$P$が経由する項を$T_{i_1},\dots,T_{i_k}$とします. badな$s$-制限$\beta$の部分割り当てを次のように拡張して得られる$(s-d)$-制限を$\gamma$とします: 制限$\beta$からスタートします. まず, 項$T_{i_1}$に対して$T_{i_1}\equiv 1$となる唯一の割り当て ($T_{i_1}$は項なのでそのような割り当ては一意に存在する) を$\beta$に追加して得られる$(s-d_1)$-制限を$\beta_1$とします. 同様の操作を続いて$T_{i_2},T_{i_3},\dots$に適用していき, $d$個の変数を固定した段階で得られる$(s-d)$-制限を$\gamma$とします (ちょうど$d$個の変数を固定するので, 最後の行はいくつかの変数が未固定になりえます).

図10. $\mathsf{info}$の例. 元の項の何番目の変数に何を代入したかという情報を保持している.

$j$回目の繰り返しにおいて$T_{i_j}$の何番目の変数に何を代入したか, という情報を$j=1$から$k$まで記述した情報$\mathsf{info}$と表すことにします.

各行$T_{i_j}$に含まれるリテラルにはデフォルトの順序がついているので, $\mathsf{info}$の情報を見ると$\beta$と$\gamma$の差分がわかります.

$\Omega$を, $\beta$を動かしたときにありうる$(\gamma, \mathsf{info})$全体の集合とし, 単射$\varphi\colon \mathcal{B}\to \Omega$を
\begin{align*}
\varphi \colon \beta \mapsto (\gamma,\mathsf{info})
\end{align*}
とします. この写像が実際に単射となっていることを確認します. つまり, $(\gamma,\mathsf{info})$から元の$s$-制限$\beta$が復元できることを確認します. この復元操作では, $\beta$を知らず$(\gamma,\mathsf{info})$のみを知っている状態なので, canonicalな決定木$\mathcal{T}$や$\beta$によって固定されない項$T_{i_1},T_{i_2},\dots$や辞書順最小のパス$P$は分からないことに注意してください. なお, 関数$f$はわかっているので$f$の情報 ($T_1,\dots,T_m$) も用いてよいです.

3.4. $(f,\gamma,\mathsf{info})$から$\beta$の復元

方針としては, $\gamma$は$\beta$に追加していくつかの変数に代入を施して得られる部分割り当てです. この「追加して固定した変数は何か」がわかれば$\beta$を復元できます. そこで$\gamma$と$\beta$の違いに着目していきます.

では, 両者の差分はどこに現れるでしょうか? $\beta$はbadな割り当てなので, $f|_\beta$の全ての項は未固定もしくは$0$に固定されます. 一方で$\gamma$は$f|_\beta$の項を先頭から順に$1$になるよう固定することで構成されています.

図11. 復元アルゴリズム.

$w$-DNF $f$のcanonicalな決定木を考えます. ここで考える$f$のcanonicalな決定木とは, 項$T_1,T_2,\dots$の順番で部分木を繋げていき, 各部分木では対応する項に含まれる変数をそのデフォルトの順序で固定していくという決定木です. 決定木を$(s-d)$-制限$\gamma$に沿って辿っていきます. 部分木を通過する際にその部分木の葉のラベルが$0$か$1$かで場合分けをします. 

1. 葉のラベルが$0$のとき

そのまま次の部分木に移動して同様に辿っていきます.

2. 葉のラベルが$1$のとき

この部分木において, $\beta$と$\gamma$の差分が現れています. この差分は$\mathsf{info}$によって取得し, 全てのラベル$0$の葉に対して再び辿っていきます. 具体的には, $\mathsf{info}$の先頭の情報 「$j_1$番目の変数に$b_1$を代入, $j_2$番目の変数に$b_2$を代入, ...」に対し, 項$T_i$の$j_1$番目, $j_2$番目, ... の変数への代入操作を$\gamma$から除去します. さらに, $\mathsf{info}$から先頭の情報を削除します. そして, 部分木の$0$の葉を全て列挙し, それぞれの葉について同様に$\gamma$に沿って部分木を辿っていきます. (復元アルゴリズムの効率性は考慮していません).

これを繰り返し, $\gamma$の全ての部分割り当てを追跡したときのパスを考えます. ケース2での列挙により, 多くのパスが列挙されることになりますが, その中で割り当ての辞書順最小のパスを再び先頭から同じ方法で$\gamma$に基づいて辿ることで, $\gamma$で固定したが$\beta$で固定しなかった変数が全てわかり, $\beta$の情報を復元することができます.

3.5. 記述長

最後に, $\gamma,\mathsf{info}$の記述長を考えます. $\gamma$は$s-d$-制限なので, ありうる$\gamma$の総数は$|\mathcal{R}_{s-d}| = \binom{n}{s-d}\cdot 2^{n-s+d} $です. 次にありうる$\mathsf{info}$の総数を考えます. $\mathsf{info}$では「$i$番目の変数に$b_i$を代入する」という情報を$d$個含んでおり, $1\le i \le w$のため, ありうる$\mathsf{info}$の総数は高々$(2w)^d$となります.

一方で, $s$-制限の個数は全部で$\binom{n}{s}\cdot 2^{n-s}$個なので, 求める確率は

\begin{align*}
\Pr_\alpha[\mathsf{DT}(f|_\alpha)>d] &\le \frac{(2w)^d\cdot \binom{n}{s-d}\cdot 2^{n-s+d}}{\binom{n}{s}\cdot 2^{n-s}} \\
&\le \left(\frac{4w s}{n-s} \right)^d
\end{align*}

となり, 主張を得ます.

埋め込みクリーク問題

与えられたグラフ$G=(V,E)$に含まれる最大クリークを求めよという問題はKarp's 21 Complete Problemの一つであり, おそらく最も有名なNP困難な問題の一つとして知られています. 本記事ではこの問題の平均時困難性について考えます. すなわち, 与えられたグラフがErdos-Renyiランダムグラフ$G(n,1/2)$のときの最大クリーク(を見つける問題)について紹介し, 関連問題として埋め込みクリーク問題を紹介します.

ランダムグラフ上の最大クリーク問題

Erdős--Rényiグラフ$G(n,1/2)$を考えます. このグラフは$n$個の頂点からなり, 各頂点のペアは独立に確率$1/2$で辺を持ちます. 言い換えれば, $n$頂点の頂点ラベル付きグラフの中から一様ランダムに選ばれたグラフが$G(n,1/2)$です. このように, 入力がランダムに生成された時に問題が効率的に解けるかどうかを議論する枠組みを平均時計算量といいます.

最大クリーク問題に戻りましょう. Erdős--Rényiグラフ$G(n,1/2)$は高確率でおよそサイズ$2\log_2 n$のクリークを持つことが示せます. ここでは厳密な証明はしませんが, なぜ$2\log_2 n$という値が出るかについて, $k$-クリークの個数の期待値を使って簡単に説明します. グラフ$G(n,1/2)$に含まれる$k$-クリークの個数を$X_k$とします. $X_k>0$ならば最大クリークのサイズは$k$以上であり, $X_k=0$ならば$k$未満となります. 頂点部分集合$S\subseteq[n]$に対し, $S$がクリークであるかどうかのindicatorを$X_S$とします. すなわち$S$が$G(n,1/2)$内でクリークになっているならば$X_S=1$, そうでなければ$X_S=0$です. 固定した$S$に対して$X_S=1$となる確率は$(1/2)^{\binom{|S|}{2}}$です. さて, $X_k = \sum_{S\subseteq[n],|S|=k} X_S$ と書けます. 期待値の線形性より, $X_k$の期待値は
\begin{align*}
\mathbb{E}[X_k] &= \sum_{S\subseteq[n],|S|=k} \Pr[X_S=1] \\
&= \binom{n}{k}\cdot 2^{-\binom{k}{2}} \\
&\approx \frac{n^k}{k!} 2^{-k^2/2} \\
&\approx 2^{-k\log_2 n - k^2/2} \\
&\approx 2^{-k(\log_2 n - k/2)}
\end{align*}
となります. 途中で突然$k!$が消えたのは, $k!=2^{(1-o(1))\cdot k\log k}$は$2^{-\binom{k}{2}}$に比べて無視できるほど小さいからです. $k\gg \log_2 n$ならば指数部が負となり$X_k$の期待値は非常に$0$に近い値となります. $k\ll \log_2 n$ならば期待値は非常に大きい値となるので, $G(n,1/2)$は$k$-クリークを含むだろうことがわかります. 前半の議論(非存在性)はMarkovの不等式, 後半の議論(存在性)はChebyshevの不等式を使うと厳密な議論にできます. 詳しく知りたい方はこちらの記事を参照してください.

すなわち, 入力が$G(n,1/2)$だと最大クリークのサイズはおよそ$2\log_2 n$であることがわかります. では, この$2\log_2 n$-クリークを見つけられるでしょうか?

成功確率の枠組み

そもそも「ランダムグラフ上で問題を解く」とはどういうことなのでしょうか?

最悪時計算量の枠組みでは, 「全ての入力に対して正しい答えを出力する」効率的なアルゴリズムの構成が焦点になっていました. 一方で平均時計算量では「全ての入力に対して」という部分を「多くの入力に対して」に緩和した枠組みを考えます. 本当はerrorless/error-proneの二つの概念があるのですが, ここではerror-proneの枠組みを考えます.

定義 (成功確率)

決定的アルゴリズム$A$は以下を満たすとき, 成功確率$\gamma$で$G(n,1/2)$上で最大クリークを解くという:
\begin{align*}
\Pr_{G \sim G(n,1/2)} [ A(G) \text{ outputs a maximum clique in }G]\ge \gamma.
\end{align*}

$A$が乱択アルゴリズムのとき, 上の確率において入力$G\sim G(n,1/2)$および$A$の内部のランダムネスについての確率をとることで成功確率を定義する.

直感的に言えば成功確率とはアルゴリズム$A$が解く(固定サイズの)入力の割合を意味します. 平均時計算量の理論では, 効率的(例えば多項式時間)なアルゴリズムの中で最大の成功確率$\gamma$をもつものが研究の対象となります.

入力によって解けるか解けないかが決まるので, 乱択アルゴリズムのように
「繰り返して成功確率を増幅させる」ことはできない.

例えば, 成功確率$\gamma=1$のアルゴリズムは最悪時の意味において最大クリーク問題を解くことを意味します. これはNP困難なので, $\gamma=1$を満たす多項式時間アルゴリズムは存在しないと広く信じられています. 従って$\gamma<1$の範囲で考えます. この記事では確率$1-o(1)$を「高確率」と呼ぶことにします(注1).

(注1). 「高確率」という言葉は専門用語として扱われることが多いです. ランダムグラフの文脈では漸近的に確率$1$で成り立つことを「a.a.s. (asymptotically almost surely)」「w.h.p. (with high probability)」と言うことがあります. また, 乱択アルゴリズムの文脈では, 何らかの定数$c>0$が存在して確率$1-n^{-c}$で成り立つことを「高確率」ということもあります.

上の定義では誤った答えを出力しうるものの常に多項式時間で終了するアルゴリズムを考えていました. このようにアルゴリズムの「誤りうる」という性質をerror-proneと言います. 一方で, 常に正しい答えを出力するが入力によっては指数時間かかりうるという性質をerrorlessといいます. 乱択アルゴリズムの文脈で例えるとラスヴェガス法か, モンテカルロ法かという話です. 

最悪時と平均時のギャップ

さて, $G(n,1/2)$上での最大クリーク問題に話を戻しましょう. 証明はしませんが, $G(n,1/2)$は確率$1-n^{-\Omega(\log n)}$で最大クリークのサイズが高々$2.01\log_2 n$であることが証明できます. 従って, サイズ$2.01\log_2 n$以下の頂点部分集合$S \subseteq [n]$ を全て列挙し, クリークをなした$S$の中で最大のものを出力すると, $n^{O(\log n)}$時間で成功確率$1-n^{-\Omega(\log n)}$で$G(n,1/2)$上で最大クリークを解けます.

最悪時の世界では最大クリーク問題はETH(強指数時間仮説)の下では$2^{\Omega(n)}$時間かかると予想されていますが, 平均時の世界では単純なbrute-forceを考えれば$n^{O(\log n)}$時間で高確率で解くことができます.

貪欲法

最大クリーク問題に対する最も単純なアプローチが貪欲法です. 何でも良いので極大クリークを一つ選び, 出力するというアルゴリズムです. 例えばクリークに追加できる頂点のうち, インデックスが一番若い頂点を選んで追加するというルールを考えてみましょう.

定理 (Karp, 1976, informal).

入力$G(n,1/2)$上の貪欲法で得られる極大クリークを$S$とすると, 確率$1-o(1)$で$|S| = (1\pm o(1))\log_2 n$を満たす.

すなわち, 貪欲法は"ほぼ2近似"アルゴリズムであるといえます. 最悪時の世界では, 任意の小さな定数$c>0$に対して最大クリークを多項式時間で$n^{1-c}$近似するのはNP困難であることが知られているので, この定理もまた最悪時と平均時の世界のギャップを意味します.

証明(の概要).
貪欲法の$t$回目の反復で得られる頂点部分集合を$S_t$とします. すなわち, $S_0=\emptyset$であり, $S_{t+1}$は$S_t\cup \{u\}$がクリークになるような頂点$u$のうち最もインデックスが若いものとします (例えば一番最初に追加される頂点は必然的に最もインデックスの若い$v_1$になります). $S_t$の要素数は$t$なので, 貪欲法が終了したときのステップ数$t$の上下界を求めればよいことになります.

この「若い頂点を優先する」貪欲法は, 頂点を$v_1,\dots,v_n$の順に見ていき初めて追加できる頂点を見つけたらそれを追加するというように実装することができます. この実装では, 例えば時刻$t$で頂点$v_i$が追加されたとすると, その反復までにアルゴリズムは以降の頂点$v_{i+1},\dots,v_n$を見ていないことになります (もちろんこれは実装依存ですが, $v_{i+1},\dots,v_n$を見ないように実装したものと同じ出力を得るので, 見ていないということを仮定できます). すなわち, この反復までの挙動は誘導部分グラフ$G[\{v_1,\dots,v_i\}]$にのみ依存するのであって, $v_{i+1},\dots,v_n$に接続する辺の情報とは独立です. ですので, 頂点$v_{i+1}$を見たとき, その時初めて辺$\{v_{i+1},v_j\}$ ($j=1,\dots,n\}$) に関する入力の情報をサンプルする (つまり, 入力を生成→アルゴリズムの解析, ではなく, アルゴリズムの反復に応じて入力を徐々に生成していく) という確率過程によってアルゴリズムの振る舞いを解析ができます.

時刻$t$における反復において$S_t$の要素数は$t$であり, $S_t$の全ての頂点と隣接している頂点が新たに$S_{t+1}$に加わるわけですが, 固定した頂点$v_j$が追加される確率は$(1/2)^t$です. 従って, 任意の定数$c>0$に対し$t\ge (1+c)\log_2 n$ならば, $v_j \in [n]$に関するunion boundより一つも頂点が追加されないので, $t \le (1+c)\log_2 n$を得ます. 逆に, $t<(1-c)\log_2 n$ならばこの確率は$n^{-1+c}$となり, 追加できる頂点の個数の期待値はおよそ$n^c$で非常に大きいので, そのような頂点は高確率で存在することになります.

$v_j$は$S_t$の全ての頂点と隣接していればクリークに追加できる.

(証明終)

衝撃的なことに, 本質的に貪欲法より良い多項式時間アルゴリズムはいまだに知られていません (それどころか存在しないと予想されています). 具体的には, 以下の主張が正しいかどうかは非常に重要な未解決問題です.

ある定数$\varepsilon>0$と多項式時間アルゴリズムが存在して, $G(n,1/2)$上で$(1+\varepsilon)\log_2 n$-クリークを確率$2/3$で見つける.

埋め込みクリーク問題

Erdős--Rényiグラフ$G(n,1/2)$上の最大クリーク問題の変種として, $k$-クリークが埋め込まれたランダムグラフから$k$-クリークを復元する問題を考えます. 具体的には, 入力として次の操作によって得られるランダムグラフ$G(n,k,1/2)$が与えられます:

1. Erdős–Rényiグラフ $G(n,1/2)$を生成する, ランダムに$k$個の頂点$v_1,\dots,v_k$を選び, $C=\{v_1,\dots,v_k\}$とする.
2. 各$1\leq i<j\leq k$に対して辺$\{v_i,v_j\}$を追加して$C$をクリークにする (元々$\{v_i,v_j\}$が辺をなす場合は追加しない).

ここで埋め込むクリークサイズ$k$は$k \gg \log n$とします. Erdős--Rényiグラフ$G(n,1/2)$はサイズが$O(\log n)$のクリークを持つので, 直感的にはサイズ$k$のクリークをランダムに埋め込むと一意になる気がします.

最大クリークのときと同様に, アルゴリズムの成功確率を以下のように定義します.

定義 (成功確率)

決定的アルゴリズム$A$は以下を満たすとき, $G(n,k,1/2)$上で成功確率$\gamma$で埋め込みクリーク問題を復元するという:
\begin{align*}
\Pr_{G \sim G(n,k,1/2)} [ A(G,k) \text{ outputs the planted $k$-clique $C$ in }G]\ge \gamma.
\end{align*}

ここでは, 簡単のため, アルゴリズム$A$はクリークサイズ$k$知っていると仮定する.

$A$が乱択アルゴリズムのとき, 上の確率において入力$G\sim G(n,k,1/2)$および$A$の内部のランダムネスについての確率をとることで成功確率を定義する.

情報理論と計算量理論のギャップ

例えば$k=2$の場合はただの辺が埋め込まれただけなので, ランダムな辺を出力するしかできないので情報理論的に成功確率の上回は$O(1/n^2)$となります. 一方で任意の定数$c>0$に対し, $k\ge (2+c)\log_2 n$のとき, $G(n,k,1/2)$は確率$1-2kn 2^{-k/2}$で$k$クリークを一つだけ含むことが初等的な数え上げで示すことができます. このとき, 全探索によって高確率で埋め込んだクリークを復元できます.

実は, $G(n,1/2,k)$上でも$k\ge (2+c)\log_2 n$であれば ($k=n^{0.1}$とかであっても), $n^{O(\log n)}$時間で$k$-クリークを確率$1-o(1)$で解くことができます. 一方で$k \le 2\log_2 n$のときはErdős--Rényiグラフ$G(n,1/2)$は$2\log_2 n$クリークを持つので情報理論的に埋め込まれた$k$-クリーク$C$を復元することはできません.

命題.

任意の定数$c > 0$および$k\ge (2+c)\log_2 n$に対し, $G(n,1/2,k)$上で成功確率$1-o(1)$で埋め込みクリーク問題を解く$n^{O(\log n)}$時間アルゴリズムが存在する. 

証明.

アルゴリズムは非常にシンプルです: サイズ$2\log_2 n$の頂点部分集合$S \subseteq V$を列挙し, もしも$S$が$G(n,1/2,k)$においてクリークをなすならば貪欲法によって極大クリークを一つ選び, そのサイズが$k$と等しいならばその極大クリークを出力する. 最終的にサイズ$k$のクリークが見つからなかったら特別な記号$\bot$ (見つからなかった, を意味する)を出力する.

列挙した各$S$に対して一つの極大クリークしか考えないので計算時間は$n^{O(\log n)}$です. あとはこれで「取りこぼしがない」ことを証明する必要があります. $C$を埋め込まれたクリークとします. 列挙したときにある$S \subseteq C
$に対して, $C$以外の頂点が貪欲法で追加され得ないことを示せばよいです. フォーマルに言うと, ある$S\subseteq C,|S|=2\log_2 n$が存在して, $C$の外側の頂点$v$であって$\Gamma(v) \supseteq S$を満たすものがないことを示せば, $V\setminus C$の頂点が貪欲法で追加され得ないため必ず極大クリークは$C$になります.

こうなるような$S$の存在性を示したい.

埋め込む位置$C$と$V\setminus C$の間の辺は全て独立なコイントスによって決まります. そこで固定した$C$で条件つけたときに所望の$S\subseteq C$が高確率で存在することが言い, その後に$C \sim \binom{[n]}{k}$に関する期待値をとれば$G(n,1/2,k)$上の確率を抑えたことになります.

固定した$C\subseteq [n]$に対し, $S\subseteq V$を$C$内からインデックスの若い$2\log_2 n$個の頂点からなる集合とします. $C$は固定されているため$S$もまた固定されています. 従って, 各$v \in V \setminus C$について$v$が$S$の全ての頂点に隣接している確率は$(1/2)^{2\log_2 n}\le n^{-2}$です (これは$S$が固定されているため, $S$の情報と辺の有無の情報が独立だから成り立つ). $v$についてのunion boundより, 確率$1-O(n^{-2})$で$\Gamma(v)\supseteq S$を満たす$v \in V\setminus C$は存在しません. すなわち, この$S$の構成は高確率で所望の性質を満たします. なお, この議論は$\log_2 n$の係数が$1$より真に大きければ同様に適用できます.

以上より, $G(n,1/2,k)$において, 埋め込んだクリーク$C$の中からインデックスの若い順に$2\log_2 n$個の頂点集合を$S$とすれば, $S$を含む極大クリークは$C$のみになりますので, 確かに列挙するアルゴリズムは埋め込みクリークを解きます. (証明終)

ここまでで単純な列挙によって$n^{O(\log n)}$時間で埋め込みクリーク問題は$k\ge 2.01\log_2 n$ならば高確率で解けることを確認し, $k\le 2\log_2 n$では情報論的に解けないことを見てきました. これは$k=2\log_2 n$が情報理論的に解けるかどうかの境界になっていると解釈できます. では, 同様の範囲の$k$で埋め込みクリーク問題を多項式時間で解けるでしょうか?

結論から言うと$k\ge \sqrt{n}$であれば確率$1-o(1)$で埋め込みクリーク問題は多項式時間で解けることが知られている[Alon, Krivelevich, Sudakov, '98]のですが, $k = o(\sqrt{n})$に対して多項式時間で解けるかどうかは30年来の未解決問題で, 実はある$c>0$に対して$k=n^{1/2-c}$に対して多項式時間で確率$2/3$で埋め込みクリーク問題を解く多項式時間アルゴリズムは存在しないのではないかと予想されています (埋め込みクリーク予想).

ここではAlonらの結果より少し弱い, $k\ge 10\sqrt{n\log n}$のときに埋め込みクリーク問題を解くアルゴリズム[Kučera, 95]を紹介します.

命題.

$k\ge 10\sqrt{n\log n}$のとき, $G(n,1/2,k)$上の埋め込みクリーク問題を高確率で解く多項式時間アルゴリズムが存在する.

証明 (概要).

アルゴリズムは「次数の大きい順に頂点を$k$個出力する」です. 埋め込まれたクリーク$C$に属する頂点は, クリークの分だけ次数が大きくなるはずであり, $k\ge 10\sqrt{n\log n}$ならばその差が有意であるという議論をします.

頂点$v \not\in C$の次数の周辺分布は二項分布$\mathrm{Bin}(n,1/2)$なので, Hoeffdingの不等式および$v$に関するunion boundより
\begin{align*}
\Pr[\exists v\not\in C,\deg(v) > n/2 + \sqrt{n\log n}] \le n\cdot \exp(-2\log n) \le n^{-1}
\end{align*}

を得ます. 一方, $v\in C$の次数の周辺分布は$k+\mathrm{Bin}(n-k,1/2)$なので, 同様にHoeffdingの不等式より, 任意の$t>0$に対し

\begin{align*}
\Pr\left[\exists v\in C,\deg(v) < \frac{n-k}{2}+k-t\right] \le n\exp\left(-\frac{2t^2}{n}\right).
\end{align*}

特に$t=4\sqrt{n\log n}$を代入すると, 確率$1-o(1)$で全ての$v\in C$は$\deg(v) \ge \frac{n}{2} + \sqrt{n\log n}$を満たします. 従って$k\ge 10\sqrt{n\log n}$のとき確かに次数を見ることで$C$が復元できます. (証明終)

Appendix. 埋め込みクリークの一意性

ランダムグラフ$G(n,k,1/2)$は埋め込まれたものが一つあるので, $k$クリークを一つ以上部分グラフとして含みます. ここでは$k\ge (2+c)\log_2 n$の場合は高確率で$k$クリークが一つであることを証明します.

この主張は直感的には自明に思えます. Erdős--Rényiグラフ$G(n,1/2)$の最大クリークは$2\log_2 n$なので, それより大きい$k$-クリークを埋め込むと確かに埋め込まれたクリーク以外に$k$-クリークは登場しなさそうです. ところが, $k$-クリークを埋め込むことによって非自明に大きいクリークが発生しうる懸念をケアしなければなりません.

$G(n,1/2,k)$における他のクリークのサイズはどのくらいになるのでしょうか? 埋め込まれたクリークを表す頂点部分集合を$C$とします. 任意の頂点$v \not \in C$は$C$内におおよそ$k/2$個の隣接点を持ちます.

これは, $v$と$C$の間の辺は独立に確率$1/2$で生起するので, $\Gamma(v)$を$v$の隣接点の頂点集合とすると, $|\Gamma(v) \cap C|$の周辺分布は$\mathrm{Bin}(k,1/2)$になり, これにHoeffdingの不等式を適用することでわかります (より詳しくいうと, 確率$1-n^{-100}$で, 全ての頂点$v$に対し$|\Gamma(v) \cap C| \le k/2 + 100\sqrt{k\log n}$がいえる.)

また, $\{v\} \cup \Gamma(v)$は$G(n,k,1/2)$内でクリークをなすので, $C$以外にも$k/2$-クリークを持つことがわかります. 実は$C$以外のクリークのサイズは全て$k/2 + O(\sqrt{k\log n}) \approx (1+o(1))k/2$以下になります.

この議論に基づくと, $k\ge 100\log_2 n$に対して$k$-クリークの一意性が証明できます (特に, Hoeffdingの不等式でネイピア数が出てくるのでlogの底に関して慎重にならなければなりません). $k\ge (2+c)\log_2 n$に対して一意性を示すにはもう少し丁寧な議論が必要です.

命題 [Theorem 4, Jerrum '92]. 任意の$k$に対して, $G(n,k,1/2)$が二つ以上の$k$クリークを含む確率は高々$2kn2^{-k/2}$である.

証明 (概要).

$V=[n]$を頂点集合, $C\subseteq V$を埋め込まれた$k$クリークとします. $C$とは別の$k$-クリーク$C' \neq C$の個数を$X$とし, その期待値を考えます. すなわち
\begin{align*}
\mathbb{E} = \sum_{C'\in \binom{V}{k},C'\neq C} \Pr[C'\text{ is a $k$-clique}]
\end{align*}

を上から抑えます. 各$t=0,1,\dots,k-1$に対し, $|C'\cap C|=t$なる$C'$を列挙して$t$に関する和を考えると

期待値$\mathbb{E}[X]$は
\begin{align*}
\mathbb{E}[X] &= \sum_{t=0}^{k-1} \binom{k}{t}\binom{n-k}{k-t}\cdot 2^{-\binom{k}{2} + \binom{t}{2}} \\
&\le \sum_{t=0}^{k-1} \left(kn 2^{-k/2}\right)^{k-t} \\
&\le kn 2^{-k/2} \cdot \sum_{t=0}^\infty (1/2)^t \\
&\le 2kn 2^{-k/2}
\end{align*}
を得ます.

STOC2日目以降の感想 (主にsunflower conjecture周り)

STOCが終わったので記憶が残っているうちに勢いに任せて前回に引き続きSTOC参加記(2日目〜5日目)を駆け足で書いていきます. 聴講して特に印象に残ったものについて記載しています. 勢いに任せて書いているのでテクニカルな内容はありません. ただし, sunflower lemmaの話については結構面白いと思ったので自分が理解した範囲で定義とかを書いていきます.

2日目

朝にLength-Constrained Expandersというワークショップに参加しました. 近年巷を騒がせているエクスパンダー分解や小直径分解という概念があるのですが, length-constrained expanderとはどちらの性質も同時に兼ね備えた分解を与える概念のようです. どちらの分解でも共通して頂点部分集合の分割$\mathcal{P}=(P_1,\dots,P_\ell)$であって, 各部分集合$P_i$のなる誘導部分グラフ$G[P_i]$が小直径または(Cheeger定数の意味で)エクスパンダーグラフとなるようなものを求めます. そして各$P_i$を縮約して得られるグラフに対して再帰的に分解を適用することによって, エクスパンダーからなる階層構造が得られます.

端的に言えば, 最悪時の問題例を分解によってエクスパンダー上で解くことに帰着するみたいなことをするようです. length-constrained expanderとは小直径分解とエクスパンダー分解両方の嬉しい性質を同時に達成するような分解らしいです.

2日目の午後は自分の発表を行いました. その次のセッションはランダムウォークなど確率解析のセッションでした. 時差ボケであまりちゃんと聞けなかったのですが最後の発表

On the Fourier Coefficients of High-Dimensional Random Geometric Graphs (Kiril Bangachev and Guy Bresler)

が印象的でした. この論文ではランダム幾何グラフとErdős--Rényiグラフの識別問題に対してよく知られる計算量と情報理論のギャップ (computational-statistical gap) について議論しており, low-degree polynomialと呼ばれるアルゴリズムのクラスでは両者のギャップが埋まる, という話でした.

3日目

午後は誤り訂正符号のセッションに行きました. 近年のTCSでは3クエリのlocally correctable codeのレートに関する効率性の下界を, これまで知られていたものより指数的に改善したという論文

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes (Pravesh K. Kothari, Peter Manohar)

の発表がありました. これはTCSの符号界隈で非常に大きな話題になりました.

その次のセッションは

Complexity-Theoretic Implications of Multicalibration, (Sílvia Casacuberta, Cynthia Dwork, Salil Vadhan)

でした. この論文はarXivに出た瞬間から個人的に注目していた論文です. additive combinatoricsにおけるdense model theorem (Green-Taoの定理の証明で重要な役割を果たした定理), Impagliazzoのhardcore補題, そしてFrieze-Kannanの正則化補題がどれも同じような構成的証明を与えていることに着目して共通の一般化を与えたという論文があるのですが, この論文はそれをmulticalibrationの観点でさらに一般化したというものです. この論文もquanta magazineの記事で紹介されています.

4日目

Applications of Turán-type problems in Theoretical Computer Scienceというワークショップに参加しました. Turánの定理とは完全グラフ$K_r$を部分グラフとして含まないグラフのうち最も辺数が多いものは, 等分割された完全$(r-1)$部グラフであるという主張です. 例えば三角形を含まないグラフの中で最もデンスなのは完全二部グラフです.

この問題は次のような自然な設定で登場します:

$n$個の電池があり, そのうち$r$個のみが充電されていて他は全て充電が空なのですが, どれが充電されていてどれが空か分からないとします. 手元には懐中電灯があり, 充電されている電池を2個入れると光ります. $n$個の中から二つの電池を入れて試すという試行を何回か行って懐中電灯を光らせたいとき, 最も試行回数を少なくするにはどうすればよいか?

グラフの言葉に翻訳すると以下になります: $n$個の頂点があってサイズ$r$の独立点集合を含まないグラフのうち最も辺数が少ないものは何か? グラフを一つ固定したとき, 各辺は懐中電灯の一回の試行に対応します. このグラフがもしもサイズ$r$の独立点集合$I$を持つならば, この頂点部分集合$I$が「充電された電池」であったときにこの試行で懐中電灯を光らせることができません. この解となるグラフの補グラフをとるとTuránの定理の設定になります.

Turán-typeな問題とは, 固定されたグラフ$H$を含まないグラフの中で最も密なものは何かという極値グラフ理論の問題です. 例えば奇数長の閉路は完全二部グラフを考えれば辺数$\Omega(n^2)$を達成しますが, 四角形を含まない任意の$n$頂点グラフは辺数が$O(n^{1.5})$になります (こちらの記事で証明しています). 応用として, ワークショップではErdősの内周予想やそれの最近の進展について取り上げられていました. 特に興味深かったのは$H=C_8$のときは未解決であるということでした. つまり, 長さ$8$の閉路を含まない$n$頂点グラフのうち最大辺数を$\mathrm{ex}(n;C_8)$とすると現在知られている最善のバウンドが

\[
\Omega(n^{6/5}) \le \mathrm{ex}(n;C_8) \le O(n^{5/4})
\]
となっており, このギャップを埋めるのはこの分野の中心的な未解決問題らしいです.

5日目

前日に引き続きTuranのワークショップに参加しました. とあるpseudorandomnessを満たす部分集合族を使ってsunflower lemmaの改善を与えた論文の話がありました. 集合$S_1,\dots,S_r \subseteq [n]$は, 全ての$i\neq j$に対して$S_i \cap S_j = S_1 \cap \dots \cap S_r$を満たすとき, $r$-ひまわりと呼びます. 

$[n]$上の集合族$\mathcal{S}=\{S_1,\dots,S_m\}$は, ある$S_{i_1},\dots,S_{i_r}\in\mathcal{S}$が$r$-ひまわりをなすとき, $r$-ひまわりを含むといいます. $r$-ひまわりを含まない部分集合族$\mathcal{S}$であって最も多くの集合を持つものはどのようなものになるでしょうか?

定理 (Erdős-Rado, '60)

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. もし$|\mathcal{S}| > w! \cdot (r-1)^w$を満たすならば, $\mathcal{S}$は必ず$r$-ひまわりを含む.

この$m$のバウンド$w!\cdot (r-1)^w$を漸近的に改善できるのではないか? というのがひまわり予想です.

予想 (Erdős-Rado, '60).

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. 各$r \ge 3$に対してある定数$C>0$が存在して, $|\mathcal{S}|>C^w$を満たすならば, 集合族$\mathcal{S}$は必ず$r$-ひまわりを含む.

Alweiss, Lovett, Wu, and Zhang (STOC20) はErdős-Radoの定理のバウンドを改善し以下の定理を証明しました:

定理 (Alweiss, et al. (2021)).

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする.  各$r \ge 3$に対してある定数$C>0$が存在して, $|\mathcal{S}|>(Cr^3 \log w \log\log w)^w$を満たすならば, 集合族$\mathcal{S}$は必ず$r$-ひまわりを含む.

ワークショップではこの定理の証明の雰囲気が紹介されました. まず, 集合族$\mathcal{S}$の擬似ランダム性を以下で定義します:

定義.

$[n]$上の部分集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. この集合族$\mathcal{S}$は, 任意の$T\subseteq[n]$に対して
\begin{align*}
\Pr_{S \sim \mathcal{S}} [ S \supseteq T ] \le \kappa^{|T|}
\end{align*}
を満たすとき, $\kappa$-spreadという.

部分集合族$\mathcal{S}=\{S_1,\dots,S_m\}$および$T\subseteq[n]$に対し, $T$のリンク$\mathcal{S}_T$とは, 部分集合族であって,
\begin{align*}
\mathcal{S}_T = \{S\setminus T \colon T \subseteq S\in\mathcal{S} \}
\end{align*}
によって定まるものです. リンクの言葉を使うと, $\mathcal{S}$が$\kappa$-spreadであるというのは, 任意の$T$のリンク$\mathcal{S}_T$が
\begin{align*}
|\mathcal{S}_T| \ge \kappa^{-|T|}\cdot |\mathcal{S}|
\end{align*}
を満たすことを意味します ($\mathcal{S}_T$の要素数は$T$を含む$\mathcal{S}$に属す部分集合の個数に等しいから).

重要な観察として, もしもリンク$\mathcal{S}_T$が$r$-ひまわり$\{S'_1,\dots,S'_r\}$を含むとしましょう. すると, $S'_1\cup T, \dots, S'_r \cup T$は$\mathcal{S}$における$r$-ひまわりになっているはずです. すなわち, リンクをとった後にひまわりがあるならば元の集合族に復元することができます.

適切な$\kappa$を選びます. もしも今持っている集合族$\mathcal{S}$が$\kappa$-spreadでないとするならば, 定義よりある$T$が存在して$|\mathcal{S}_T| > \kappa^{|T|}\cdot |\mathcal{S}|$となります. このリンク$\mathcal{S}_T$に対してひまわりの存在性を言えば, $\mathcal{S}$がひまわりを持つことが示せます. これを再帰的に繰り返していくと, $\kappa$-spreadingな集合族に対して議論すれば良いことになります. Alweissらの貢献は$\kappa$-spreadingな集合族に対してはdisjointな部分集合$S_{i_1},\dots,S_{i_r}$がとってこれることを示したこと(らしい)です. disjointな部分集合族はひまわりをなすので, これで定理の主張が証明できたことになります.

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

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

• 疎な正則エクスパンダーグラフ
• 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).

まとめ

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

擬似ランダム生成器とNisan-Wigderson生成器

1. 擬似ランダム生成器

平均時計算量では分布のランダムっぽさを, その分布が任意の効率的な敵対者(=アルゴリズム)に対して一様分布と識別できないという性質によって定義する定式化があります. ここでは主に敵対者としてサイズ$s$の回路を考えます. 前回の記事でも紹介しましたが分布の擬似ランダム性を以下で定義します:

定義1 (擬似ランダム性).

$\{0,1\}^\ell$上の分布$D$がサイズ$s$に対して$\epsilon$-擬似ランダムであるとは, 任意のサイズ$s$の回路$C$に対して

\begin{align*}
|\mathbf{E}_{x\sim D}[C(x)]-\mathbf{E}_{x\sim U_n}[C(x)]| \leq \epsilon
\end{align*}

が成り立つことをいう (ここで$U_n$は$\{0,1\}^n$上の一様分布). 

定義2 (擬似ランダム生成器).

関数$G\colon \{0,1\}^n\to\{0,1\}^\ell$は, $\{0,1\}^\ell$上の分布$G(U_n)$がサイズ$s$に対して$\epsilon$-擬似ランダムであるとき, サイズ$s$に対する$\epsilon$-擬似ランダム生成器であるという.

擬似ランダム生成器は短いランダム文字列を受け取って長い擬似ランダム文字列を返す関数です. 例えば$\ell$ビットのランダム文字列$r$を使う乱択アルゴリズム$\mathcal{A}(x;r)$を考えたとき, $r$としてランダム文字列の代わりに$G(U_n)$を用いたアルゴリズム$\mathcal{A}(x;G(U_n))$もまた元の乱択アルゴリズム$\mathcal{A}(x;r)$とほぼ同じ振る舞いをすることが示せます (そうでないとすると, $\mathcal{A}(x;\cdot)$を使って$G(U_n)$と$U_\ell$を識別できるので). 全ての$n$ビットのシードを列挙すれば, $2^n$倍のオーバーヘッドでアルゴリズムを脱乱択することができます. このように考えると, $\ell$が大きいかつ$\epsilon$が小さいほど擬似ランダム生成器は良いということになります.

2. 簡単な例

2.1. 1ビットだけ伸ばす

前回の記事の定理(Yaoのnext-bit predictor)により, 関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon)$困難であるならば, 関数$G\colon x\mapsto (x,f(x))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダム生成器になります. この関数$G$は$\ell=n+1$なので, 1ビットだけ伸ばす擬似ランダム生成器です.

定理1.

関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon)$-困難ならば, 関数$G\colon x\mapsto (x,f(x))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダム生成器である.

2.2. 2ビットだけ伸ばす

関数$G\colon \{0,1\}^{2n}\to \{0,1\}^{2n+2}$を

\begin{align*}
G(x,y)=(x,f(x),y,f(y))
\end{align*}

としてみます (ここでは入力を前半と後半の$n$ビットずつに区切り, それぞれを$x,y\in\{0,1\}^n$としている). 同様の議論を使うとこれは2ビットだけ伸ばす擬似ランダム生成器になることが示せます.

定理2.

関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon/2)$-困難ならば, 関数$G\colon (x,y)\mapsto (x,f(x),y,f(y))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダム生成器である.

証明:

背理法で示す. あるサイズ$s'$の回路$C$が存在して

\begin{align*}
\mathbf{E}_{(x,y)\sim U_{2n}}[C(x,f(x),y,f(y)] - \mathbf{E}_{(z,w)\sim U_{2n+2}}[C(z,w)]>\epsilon
\end{align*}

となるとする (必要があれば出力ビットを反転することで絶対値を外せる). 期待値の線形性およびランダム文字列をそれぞれ$z=(x,b),w=(y,c)$と書き直すと

\begin{align*}
\mathbf{E}_{(x,b,y,c)\sim U_{2n+2}}[C(x,f(x),y,f(y)) - C(x,b,y,c)] > \epsilon
\end{align*}

を得ます. この式の左辺は, 同じ値を足したり引いたりすることで

\begin{align*}
\mathrm{(LHS)} &= \mathbf{E}[C(x,f(x),y,f(y))] - \mathbf{E}[C(x,f(x),y,c)] \\
&\hspace{1em}+ \mathbf{E}[C(x,f(x),y,c)] - \mathbf{E}[C(x,b,y,c)] > \epsilon
\end{align*}

を得ます. よって, 前半の差と後半の差の少なくとも一方は$>\epsilon/2$です. すなわち

\begin{align*}
&\mathbf{E}[C(x,f(x),y,f(y))] - \mathbf{E}[C(x,f(x),y,c)] > \epsilon/2 \\
&\hspace{10em}\text{ or }\\
&\mathbf{E}[C(x,f(x),y,c)] - \mathbf{E}[C(x,b,y,c)] > \epsilon/2
\end{align*}

です. もし前者が成り立つならば, ある$x^*\in\{0,1\}^n$が存在して回路$C'(y,c):=C(x^*,f(x^*),y,c)$を考えると, これは二つの分布$(y,f(y))$と$U_{n+1}$をアドバンテージ$>\epsilon/2$で識別する. これは定理1に反する. 後者が成り立つ場合でも同様に, 回路$C$においてうまく$(y,c)\in\{0,1\}^{n+1}$を選んで固定して得られる回路$C'$は定理1に反する.

(証明終)

コメント1. 上記の証明において, 回路の入力を部分的にうまく選んで固定して新しい回路を得ていました. 例えば前半のケースでは$x$を固定していましたが, このときの$x$の選び方は$(y,c)$の選び方には依存しないことに注意してください. また, $x$を固定すると$f(x)\in\{0,1\}$も自動的に固定されます. このように回路の入力を部分的にうまく選んだ値に固定することをハードワイヤ (hardwire)するといいます.

コメント2(適当に読み飛ばしてください). 上記の証明においては同じ値を足したり引いたりしてうまく式変形した後に, 二つのケースに分けてそれぞれについて$(U_n,f(U_n))$と$U_{n+1}$を識別する回路$C'$を構成しました. このときの式変形では, 

\begin{align*}
\mathbf{E}[C(D)]-\mathbf{E}[C(D')]>\epsilon
\end{align*}

の形をした左辺を二つの差分の和として表現していて, それぞれの差分では構成要素が一つしか異ならないテレスコープサムのような形に変形しています. このように, 二つの$D$と$D'$を補間するような分布列$D_0=D,D_1,\dots,D_k=D'$を用意して

\begin{align*}\mathbf{E}[C(D)]-\mathbf{E}[C(D')]=\sum_{i=1}^k \mathbf{E}[C(D_{i-1})-C(D_i)] >\epsilon \end{align*}

と式変形して議論することをハイブリッド議論 (hybrid argument)と呼び, 分布列$D_0,\dots,D_k$をハイブリッド分布と呼びます (平均時計算量の脱乱の分野では頻出です).

コメント3. 上記の証明ではあくまでも回路の存在性のみをいっていて, その回路が効率的に構築できるかどうか (つまり元となる回路$C$を入力として受け取って所望の回路$C'$を出力するアルゴリズムの存在性) については何も言っていないことに注意してください. 例えば$x=x^*$にハードワイヤする際に$f(x^*)$も同時にハードワイヤしましたが, このとき$f(x^*)$を計算する手間は考えていません ($x^*$を固定したら一意に定まるから).

2.3. 2ビット伸ばす (続)

2.2節では$2n$ビットのランダム文字列を受け取って$2n+2$ビットの擬似ランダム文字列を出力する擬似ランダム生成器を紹介しました. ここでは, 次の章のために別の擬似ランダム生成機$G\colon \{0,1\}^{2n-d} \to \{0,1\}^{2n-d+2}$を紹介します ($d$はパラメータ).

まず, $2n-d$ビットの入力$z\in\{0,1\}^{2n-d}$の前半$n$ビットを$x$, 後半$n$ビットを$y$とします. 関数$G(z)$は$(z,f(x),f(y))$を出力します.

$d=0$のときは2.2節と同じになりますが, ここでは$x$と$y$の取り方にオーバーラップを許している点が異なります. このように構成された$G''$も$d$が小さければ擬似ランダム生成器になることが示せます:

定理3.

関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon/2)$-困難であるならば,上記で定義された関数$G$はサイズ$s-2^{O(d)}$に対して$\epsilon$-擬似ランダム生成器である.

証明する前にまず, そもそも2.2節の議論で示せないか考えてみましょう. 2.2節の議論では, 二つの分布$(x,f(x),y,f(y))$と$(x,b,y,c)\sim U_{2n+2}$が識別できるならばうまく$(y,c)\in\{0,1\}^{n+1}$をハードワイヤすることで$(x,f(x))$と$U_{n+1}$を識別する回路が作れて定理1に反するという方針でした. つまり, 入力を部分的に固定することで$(x,f(x))$と$U_{n+1}$を識別する回路が作れてしまうというのが2.2節の議論のミソでした (下図).

2.2節の議論で構成した回路$C'$ (二つ目のケースを図示).

今回の$G''$にこの議論を適用してみましょう. つまり, $(z,f(x),f(y))$と$(z,b,c)$を識別する回路$C$が作れたとします. 本来であれば$(y,c)$をうまくハードワイヤして得られた回路$C'$は$(x,f(x))$と$U_{n+1}$を識別することを言いたいのですが, $x$と$y$にはサイズ$d$のオーバーラップがあるので, $y$に該当する$n$ビットを固定してしまうと$x$の最後の$d$ビットも巻き込まれてハードワイヤされてしまいます. 従って, $(y,c)$をハードワイヤして得られる回路は$C'\colon \{0,1\}^{n-d+1}\to\{0,1\}$となっており, そもそも入力として$(x,f(x))$を受付けてくれません.

単純なアイデアですが, この問題点は$x$とオーバーラップしていない部分をハードワイヤすることによって解決できます. 

命題2の証明.

ビット列$w\in\{0,1\}^\ell$および$1\leq a\leq b\leq \ell$に対して$w[a:b]$を$w$の第$a$番目から$b$番目までの部分文字列とする.

$G(U_{2n-d})$と$U_{2n-d+2}$をアドバンテージ$>\epsilon$で識別する回路を$C$とする. 与えられた$z\in\{0,1\}^{2n-d}$に対し, 前の$n$ビットを$x=z[1:n]$, 後ろの$n$ビットを$y=z[n-d,2n-d]$とする. 定義より, $b,c\sim U_1$とすると,

\begin{align*}
\mathbf{E}[C(z,f(x),f(y)) - C(z,b,c) > \epsilon.
\end{align*}

この式の左辺は

\begin{align*}
(\mathrm{LHS}) &= \mathbf{E}[C(z,f(x),f(y))] - \mathbf{E}[C(z,f(x),c)] \\
&\hspace{1em}+\mathbf{E}[C(z,f(x),c)]-\mathbf{E}[C(z,b.c)] > \epsilon
\end{align*}

より,

\begin{align*} &\mathbf{E}[C(z,f(x),f(y))] - \mathbf{E}[C(z,f(x),c)] > \epsilon/2 \\&\hspace{10em}\text{ or }\\&\mathbf{E}[C(z,f(x),c)]-\mathbf{E}[C(z,b,c)] > \epsilon/2\end{align*}

を得る. 

(i). 前者が成り立つ場合, $x$の前から$n-d$ビット$x[1:n-d]$をある$w^*\in\{0,1\}^{n-d}$にハードワイヤする. このとき, $x$は$w^*$と$y[1:d]$を結合した文字列となるので, $f(x)=f(w^*,y[1:d])$の形で書くことができる. $y$が変数ならばこの値は$d$個の変数にしか依存しない値なので, サイズ$2^{O(d)}$の回路で計算できる (つまり, 固定した$w^*$に対して関数$(w^*,y[1:d])\mapsto f(w^*,y[1:d])$を計算するサイズ$2^{O(d)}$が存在する). この回路を$C$の$f(x)$を受け取る部分にくっつけます(下図).

このようにして得られた回路を$D(y,c)$とすると, $D$のサイズは$s'+2^{O(d)}$となり, $(y,f(y))$と$(y,U_1)$をアドバンテージ$>\epsilon/2$で識別する.

(ii). 後者が成り立つ場合も同様にして$(x,f(x))$と$(x,U_1)$をアドバンテージ$>\epsilon/2$で識別する回路を構成できる. こちらは単純に$y$の後ろ$n-d$ビットと$c$をハードワイヤすればよい.

ケース(i),(ii)どちらにしても所望の回路が構成できたので, 主張を得る.

(証明終)

3. Nisan-Wigderson生成器

ここまで定義した擬似ランダム生成機は2ビット程度しか伸ばさない, 少々心許ないものでしたが, 実は次数的に伸ばせることが知られています. NisanとWigdersonによるとても格好良いタイトルの論文「Hardness vs Randomness」は, 非常に困難な関数$f$を使って擬似ランダム生成器を構成する手法を提案しています. この手法によって構成された擬似ランダム生成器はNisan-Wigderson生成器と呼ばれ, 非常に強力なツールとして知られています.

2.2節と2.3節で紹介した擬似ランダム生成器$G$はどれも入力$z$から$n$ビットの文字列$x,y$を二つ取り出し, $(z,f(x),f(y))$を出力するというものでした. また, $x$と$y$のオーバーラップの長さ$d$が小さくてもサイズ$2^{O(d)}$の回路をくっつければ$G$の擬似ランダム性を示せることを2.3節で示しました. ここで, そもそも取り出す文字列は二つでなく三つ以上でも同様の証明が機能するという点に着目します. これをもとに設計されたのがNisan-Wigderson生成器です.

3.1. Combinatorial Design

定義4.

台集合$[m]$上の部分集合族$\mathcal{S}=\{S_1,\dots,S_\ell\}$が以下を満たすとき, $(m,n,d)$-デザインと呼ぶ:

(1). 各$S_i$は$|S_i|=n$.

(2). 全ての$1\leq i<j\leq \ell$に対し, $|S_i\cap S_j|\leq d$.

$(m,n,d)$-デザインは2.3節で考えた部分文字列の取り出し方を一般化したものになっています.

定理5 (Nisan-Wigderson生成器).

$\mathcal{S}=\{S_1,\dots,S_\ell\}$を$(m,n,d)$-デザインとし, $f\colon\{0,1\}^n\to\{0,1\}$を$(1/2-\epsilon/\ell)$-困難であるとする. 関数$G^f_{\mathcal{S}}\colon \{0,1\}^m\to\{0,1\}^\ell$を

\begin{align*}
G^f_\mathcal{S}(x) = (f(x|_{S_1}), \dots, f(x|_{S_\ell}))
\end{align*}

で定義する ($x|_S\in\{0,1\}^{|S|}$は$x$の$S$への制限. このとき, $G$はサイズ$s-\ell 2^{O(d)}$に対し$\epsilon$-擬似ランダム生成器である.

証明は定理3と同様なので, 概略だけ記します.

証明概略. $G^f_{\mathcal{S}}(U_m)$と$U_\ell$をアドバンテージ$>\epsilon$で識別する回路を$C$とします. 簡単のため, $x_i=x|_{S_i}$と表します. $b_1,\dots,b_\ell\sim U_1$とします. 定義より

\begin{align*}
\mathbf{E}[C(f(x_1),\dots,f(x_\ell))] - \mathbf{E}[C(b_1,\dots,b_\ell)]>\epsilon.
\end{align*}

ハイブリッド議論を見据えて式変形しましょう. $D_i=(f(x_1),\dots,f(x_i),b_{i+1},\dots,U_\ell)$とすると, $D_0=(b_1,\dots,b_\ell)$かつ$D_\ell=(f(x_1),\dots,f(x_\ell))$なので

\begin{align*}(\mathrm{LHS})&= \mathbf{E}[C(D_\ell)]-\mathbf{E}[C(D_0)] \\&=\sum_{i=1}^\ell\mathbf{E}[C(D_i)-C(D_{i-1})] > \epsilon\end{align*}

より, ある$i\in[\ell]$に対して

\begin{align*}
&\mathbf{E}[C(f(x_1),\dots,f(x_{i-1}),f(x_i),b_{i+1},\dots,b_\ell)] - \\
&\mathbf{E}[C(f(x_1),\dots,f(x_{i-1}),b_i,b_{i+1},\dots,b_\ell)] > \epsilon/\ell
\end{align*}

です. $C$の引数は$i$番目だけ異なっていることに注意してください. 変数名を$x_i=y$と変えて, $y$に対応する部分以外全てのビットをハードワイヤします (つまり$x|_{[m]\setminus S_i}=w^*$と固定する). さらに, $b_{i+1},\dots,b_\ell$もハードワイヤします. すると, $f(x_1),\dots,f(x_{i-1})$はそれぞれ, $y\in\{0,1\}^n$のうち高々$d$ビットにしか依存しません ($\mathcal{S}$が$(m,n,d)$-デザインだから). よってこれらはサイズ$2^{O(d)}$の回路で計算できるので, これらを$C$にくっつけることによって$(y,f(y))$と$(y,U_1)$をアドバンテージ$>\epsilon/\ell$で識別する回路を得ました.

(証明終).

3.2. デザインの存在性

以前の記事で証明しましたが, パラメータ$n,d\in\mathbb{N}$に対し, $\ell=n^{d+1}$個の集合からなる$(n^2,n,d)$-デザイン$\mathcal{S}=\{S_1,\dots,S_\ell\}$が存在します. このデザインを使うとNisan-Wigderson生成器は

\begin{align*}
G\colon \{0,1\}^{n^2}\to \{0,1\}^{n^{d+1}}
\end{align*}

となります.

4. Hardness vs Randomness

ここまでの定理では

$\exists $平均的に非常に困難な関数 $\Rightarrow$ $\exists$擬似ランダム生成器

という形の結果を証明しました. このように, 関数の困難性を利用して擬似ランダムネスを生み出す枠組みはHardness vs Randomnessと呼ばれ, 平均時計算量の理論で近年も活発に研究されています.