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*}

となり, 主張を得ます.