読書メモ: スパンプログラム

Karchmer and Wegderson は 1993 年にブール関数を計算する興味深い線形代数モデルスパンプログラム (span program) を発表した。ある関数 \(f(x_1,\ldots,x_n)\) に対するスパンプログラムは、変数 \(x_i\) とその否定 \(\bar{x}_i\) でラベル付けされた行を持つ、ある体 (field) 上の行列として表される (一つの変数が複数の行をラベル付けしてもよい)。入力によってラベルが満たされる行の線形結合として all-1 ベクトルを得られる場合に限り、スパンプログラムは入力割当を受け付ける。スパンプログラムのサイズは行列の行数である。正のリテラルのみが行のラベルとして使用されている場合、つまり否定の変数が許可されていない場合、スパンプログラムは単調 (monotone) である。

このモデルは非常に強力なようだ: スイッチングネットワークやド・モルガンの公式といったブール関数を計算するための古典的なモデルは、サイズを増加させることなくスパンプログラムによってシミュレートすることができる。したがって単調スパンプログラムであってもサイズの下限を証明することは困難な作業である。

Table of Contents

1. 16.1 モデル
2. 16.2 スパンプログラムとスイッチングネットワーク
3. 16.3 単調スパンプログラム
   1. 16.3.1 しきい値関数
   2. 16.3.2 非二部グラフ
   3. 16.3.3 奇数因数
   4. 16.3.4 しきい値関数の下限
4. 16.4 一般的な下限
5. 16.5 明示的な自己回避ファミリ
6. 演習
7. 参考文献

16.1 モデル

\(\mathbb{F}\) を体としたとき、\(\mathbb{F}\) 上のスパンプログラムはリテラル \(x_1,\ldots,x_n,\) \(\bar{x}_1,\ldots,\bar{x}_n\) でラベル付けされた行列 \(M\) で表される。ラベルが入力 \(a=(a_1,\ldots,a_n) \in \{0,1\}^n\) で満たされている行を保持することで得られた \(M\) の部分行列を \(M_a\) とする。つまり \(M_a\) は \(a_i=1\) となる \(x_i\) と \(a_i=0\) となる \(\bar{x}_i\) でラベル付けされている。要素が全て 1 のベクトル \(\vector{1}\) (または事前に固定された他のベクトル) が \(M_a\) の行の範囲に含まれている場合、プログラム \(M\) は入力 \(a\) を受け入れる。スパンプログラムが入力 \(a\) を受け入れるとき、まさにブール関数 \(f\) を計算し \(f(a)=1\) となる。スパンプログラムのサイズはその行数を表している。

行列の列はサイズには数えない。スパンプログラムが計算する関数を変更せずにプログラムの行列を線形独立列の集合に制限することは常に可能である。従って行よりも多くの列を使用する必要はない。ただ、通常は多くの列を含むスパンプログラムを設計する方が簡単である。列の多くは線形に依存するかもしれない。

16.2 スパンプログラムとスイッチングネットワーク

ブール関数を計算する最も古いモデルの一つはスイッチングネットワークである。このモデルはド・モルガンの公式も含んでおり、50 年前に C.E. Shannon が導入して以来、集中的に研究されてきた。

スイッチングネットワークは 2 つの頂点 \(s,t \in V\) を持つグラフ \(G = (V,E)\) で表される。その辺 (edge) は \(x_i\) または \(\bar{x}_i\) でラベル付けされている。\(G\) は複数の辺を持ち、そのいくつかは同じ endpoint を共有している。\(G\) のサイズは辺の数である。入力 \(a=(a_1,\ldots,a_n)\) は次のルールでラベル付けされた辺をスイッチする: \(x_i\) でラベル付けされた辺は \(a_i=1\) の時 on であり \(a_i=0\) の時 off である。\(\bar{x}_i\) は \(a_i=1\) の時 off で \(a_i=0\) の時 on である。スイッチングネットワークは、全ての辺を \(a\) に適用したとき \(s\) から \(t\) への経路が存在するとき \(a\) を受け入れるという方法でブール関数を自然に計算する。また非常に特殊なタイプとしてド・モルガンの公式を表すこともできる。

定理 16.1 (Karchmer-Wigderson 1993) . ブール関数がサイズ \(s\) のスイッチングネットワークで計算可能な場合、任意の体上で最大でもサイズ \(s\) でスパンプログラムを計算可能である。

証明. ある頂点 \(s,t \in V\) を含む \(G=(V,E)\) を関数 \(f\) のスイッチングネットワークとする。体 \(\mathbb{F}\) を修正し \(\mathbb{F}\) 上の \(|V|\) 次元空間の標準基底 \(\{e_i:i\in V\}\) を取得する。つまり \(e_i\) は \(i\) 番目の要素一つに正確に 1 を持つ長さ \(|V|\) の二進数ベクトルである。∎

スパンプログラム \(M\) は次のように構成される: \(E\) 内の各辺 \(e=\{i,j\}\) は \(M\) に行 \(e_i\)-\(e_j\) を追加し、\(e\) のラベルでこの行をラベル付けする。\(M_a\) の列がベクトル \(e_s\)-\(e_t\) にまたがっている場合に限り \(G\) には \(s-t\) 経路が存在し、その全てのラベル付き辺が \(a\) によって on にされることは容易に分かる。したがって \(M\) は \(f\) を計算し、そのサイズは \(|E|\) である。

16.3 単調スパンプログラム

行のラベルが正のリテラル \(x_1,\ldots,x_n\) のみで構成されているスパンプログラムは単調 (monotone) と呼ばれる。ブール関数 \(f(x_1,\ldots,x_n)\) は全ての \(i\) に対して \(a_i \le b_i\) である限り \(f(a_1,\ldots,a_n) \le f(b_1,\ldots,b_n)\) であるなら単調である。そのようなプログラムが単調関数のみで計算できることは明かである; さらに全ての単調ブール関数は単調スパンプログラムで計算することができる。

これまでに知られている (非単調) スパンプログラムサイズの最大の下限は \(\Omega(n^{\frac{3}{2}}/\log n)\) であり、これは Nechiporuk (1996) によるスイッチングネットワークサイズの下限に従っている。この議は与えられたブール関数のサブ関数の数を数え上げることに基づいており下限を大きくすることはできない。

単調スパンプログラムでの状況はこれより遙かに良い: ここで我々は超多項式の下限を証明することができる。\(n^{\Omega(\log n / \log \log n)}\) の境界は Babai ら (1996) と Babai, Gál, and Wigderson (1996) によって、ある特性を持つ二部グラフ (bipartite graphs) の異なる特性を用いて初めて得られた。そして Gál (1996) は基礎となる二部グラフの異なる特性を用いてこれらの下限を \(n^{\Omega(\log n)}\) に簡素化し改善した。

これらの証明はすべて Beimel, Gál, and Paterson (1996) によって発見されたこのようなプログラムの一般的な組み合わせの下限に基づいている。これらの証明の興味深い点は、単調スパンプログラムのサイズの下限問題を、特定のベクトル集合が線形独立であるという証明に縮小させていることである。この基準は、明示的なブール関数への適用とともに、最近の計算機科学における線形代数法の最も興味深い応用の一つである。これらの結果の力を認識するために、まず、一見難しい関数が驚くほど小さな単調スパンプログラムによって計算できることを示す。

16.3.1 しきい値関数

\(k\)-しきい値関数 \(T_k^n(x_1,\ldots,x_n)\) は \(x_1+\cdots+x_n \ge k\) の場合にのみ 1 を出力する。

命題 16.2 (Karchmer-Wigderson 1993) . \(\mathbb{F}\) を少なくとも \(n+1\) の要素を持つ体とする。このとき任意の \(1 \le k \le n\) に対して関数 \(T_k^n\) はサイズ \(n\) の \(\mathbb{F}\) 上の単調スパンプログラムによって計算することができる。

証明. (省略) ∎

\(l \gt \log n\) (これは体要素の二進数エンコーディングに相当する) となる最小の整数との \(\mathbb{F}=GF(2^l)\) を取ると、\(\mathbb{F}\) 上に構築されたスパンプログラムをサイズ \(O(n \log n)\) の体 \(GF(2)\) 上のプログラムに縮小することができる (詳細は Karchmer-Wigderson (1993) 参照)。

16.3.2 非二部グラフ

頂点集合を 2 つの独立した集合に分離できる場合、グラフは二部 (bipartite) である; それらの間に辺が存在しなければ頂点集合は独立している。異なる部の 2 つの頂点すべてが辺で結合されているとき二部グラフは完全である。

可能な辺ごとに一つの \(n=\left(\begin{array}{c}m\\2\end{array}\right)\) 変数で表される \(m\) 個の頂点上の無向グラフを入力とする関数 \({\it Non\mbox{-}Bipartite}_n\) を考えると、グラフが二部グラフでない場合にのみ関数の値は 1 となる。

定理 16.3 (Beimel-Gál-Paterson 1996) . 関数 \({\it Non\mbox{-}Bipartite}_n\) はサイズ \(n\) の単調スパンプログラムによって体 \(\mathbb{F}_2\) 上で計算することができる。

証明. (省略) ∎

16.3.3 奇数因数

グラフ \(G=(V,E)\) のスパンニング部分グラフは \(F \subseteq E\) となるグラフ \(G'=(V,F)\) である。頂点の集合が同じであることに注意。グラフの (接続された) コンポーネントは頂点の最大集合であるため、任意の 2 つの頂点の間には経路が存在する。グラフが 1 つのコンポーネントのみで構成されている場合、グラフは接続されている。頂点 \(i\) の次数 \(d_E(i)\) は \(i\) に入射する \(E\) の辺の数である。

グラフ内の奇数因数は、すべての次数が奇数であるスパニング部分グラフである。奇数因数は次のような特性を必要とする。

補題 16.4 . もしグラフが接続されているなら、頂点の数が偶数の場合にのみグラフは奇数因数を持つ。

証明. (省略) ∎

ここで \(n=m^2\) 変数上の次の関数 \({\it Oddfactor}_n\) について考える: 入力は各部に \(m\) 個の頂点を持つ二部グラフ \(X\) を表す \(m \times m\ 0\mbox{-}1\) 行列である; グラフ \(X\) は奇数因数を持つ場合に受け入れられる。補題 16.4 により頂点の数が奇数のコンポーネントがある場合 \(X\) は明確に拒否される事に注意。

定理 16.5 (Babai-Gál-Wigderson 1996) . \({\it Oddfactor}_n\) はサイズ \(n\) の単調スパンプログラムによって体 \(\mathbb{F}_2\) 上で計算することができる。

証明. (省略) ∎

\({\it Oddfactor}_n\) に対するこのスパンプログラムの単純さにもかかわらず、関数自体は完全マッチング問題に近い親和性を持ち、それが単調 Boolean モデルを困難にしている。つまり Razborov (1985b) は、全ての完全なマッチングを受け入れ全ての 2-coloring の一定の割合を拒絶する、(AND と OR を持つが NOT ゲートのない) 任意の単調回路の大きさの \(n^{\Sigma(\log n)}\) 下限を証明した。

全ての完全マッチングは奇数因数であり受け入れられるべきであることに注意。拒否されたグラフの場合は、すべての単調辺のグラフで \(V\) の 2-coloring を識別する。したがって、奇数 2-coloring (それぞれの色が奇数の頂点を占める) は 2 つの奇数コンポーネントを持ち、拒絶されなければならない。奇数 2-coloring はすべての 2-coloring の半分を構成するため Razborov の論は \({\it Oddfactor}_n\) を計算する任意の単調ブーリアン回路のサイズに \(n^{\Sigma(\log n)}\) 下限を与える。

このように、いくつかの明示的なファミリーが大きな単調スパンプログラムを必要とすることを証明することは、単調ブーリアン回路の場合よりも困難な作業である。この課題 (スパンプログラムのサイズの大きな下限) は最近線形代数のアーギュメントを用いて Beimel ら (1996), Babai ら (1996), Babai ら (1999) および Gál (1998) によって解決された。

しかし、これらの美しい結果に話を進める前にしきい値関数のもう 1 つの直接的な議論を説明する。

16.3.4 しきい値関数の下限

しきい値関数 \(T_k^n\) は少なくとも \(k\) 個の 1 を有する場合にのみ入力ベクトルを受け入れる事を述べた。この関数は大きな体上で小さな単調スパンプログラムを持ち、\(\mathbb{F}_2\) 上で関数 \(T_k^n\) はサイズ \(O(n \log n)\) の単調スパンプログラムによって計算できることをセクション 16.3.1 で述べた。それでは下限を証明しよう。

定理 16.6 (Karchmer-Wigderson 1993) . 体 \(\mathbb{F}_2\) 上で \(T_2^n\) を計算する任意の単調スパンプログラムは少なくとも \(n \log n\) のサイズを持つ。

証明. (省略) ∎

16.4 一般的な下限

スペルナーシステム (Sperner system; または antichain) は集合のファミリーであり、そのどれもが他のファミリーのメンバーを含まないことをを思い出せ。フィルタとは上向きに閉じられたファミリである: \(A \in \mathcal{F}\) かつ \(A \subseteq B\) であれば \(B \in \mathcal{F}\) である。フィルタの最小メンバーはスペルナーシステムを形成する; また各スペルナーシステム \(\mathcal{F}\) はフィルタ (そのメンバーの、必ずしも適切なスーパーセットではないすべてで構成される) を一意に定義する。

スペルナーシステムと単調ブール関数の間には 1 対 1 の対応がある。単調ブール関数の最小項は値 1 が割り当てられた場合、残りの変数に割り当てられた値に関係なく、関数に値 1 を強制する最小の変数集合である。1 のすべての最小項の集合がスペルナーシステムを形成し、すべてのスペルナーシステムが単調ブール関数を (一意に) 定義することは明らかである。

定義 16.7. スペルナーシステム \(\mathcal{F}\) は、以下のように \(H\) のコアと呼ばれるそれぞれの \(H \in \mathcal{F}\) に集合 \(T_H \subseteq H\) を関連付けることができるのであれば自己回避 (self-avoiding) である。

1. \(T_H\) がファミリ内の \(H\) を決定する。つまり、ファミリ \(\mathcal{F}\) 内の他の集合がいずれも部分集合として \(T_H\) を含んでいない。
2. 全ての \(H \in \mathcal{F}\) と部分集合 \(Y \subseteq T_H\) に対して、集合 \[ S(Y) \rightleftharpoons \bigcup_{A \in \mathcal{F}, A \cap Y \neq \emptyset}{A - Y} \] は \(Y\) の広がり (spread) と呼ばれ、\(F\) のどのようなメンバーも含んでいない。

スパンプログラムのサイズには、次の一般的な組み合わせの下限がある。

定理 16.8 (Beimel-Gál-Paterson 1996) . \(f\) を単調ブール関数とし \(\mathcal{F}\) をその最小項のファミリとする。もし \(\mathcal{F}\) が自己回避的であれば、すべての体 \(\mathbb{F}\) において、\(f\) を計算する \(\mathbb{F}\) 上のすべての単調スパンプログラムは最低でも \(|\mathcal{F}|\) のサイズを持つ。

証明. (省略) ∎

16.5 明示的な自己回避ファミリ

定理 16.8 が単調スパンプログラムのサイズに大きな下限を与えるためには、自己回避的で多くの集合を持つ明示的なスペルナーシステムが必要である。Gál (1998) は二部ぺーリーグラフ (bipartite Paley graph) の特定の特性に基づいた、このようなシステム非常にエレガントな構造を発見した。我々はこの特性をすでにセクション 15.2.2 で使用しており、これを "孤立隣接条件" (isolated neighbor condition) と呼んだ (定義 11.7 参照)。ここでこの条件を再掲する。

\(G=(V_1,V_2,E)\) を二部グラフとする。\(A \subseteq V_1\) に対して \[ \Gamma(A) \rightleftharpoons \{ u \in V_2: (v,u) \in E \ \mbox{for all} \ v \in A \} \] を \(A\) 内の頂点の共通の隣接の集合とし、\[ \hat{\Gamma}(A) \rightleftharpoons \{ u \in V_2: (v,u) \not\in E \ \mbox{for all} \ v \in A \} \] を \(A\) の全ての共通非隣接の集合とする。グラフ \(G\) は \(|A|+|B|=k\) となるような任意の 2 つの素集合 \(A,B \subseteq V_1\) に対して \(\Gamma(A) \cap \hat{\Gamma}(B) \neq \emptyset\) であれば \(k\) に対する孤立隣接条件を満たす。

\(\mathcal{F}_{G,k}\) をすべての部分集合 \(A \cup \Gamma(A)\) のファミリとする。ここで \(A \subseteq V_1\), \(|A|=k\) である。\(F_{G,k}\) がスペルナーシステムであることは明らかである。定理 16.8 で与えられる一般的な下限を適用するには、このファミリが自己回避的であることを証明する必要がある。

補題 16.10 (Gál 1998) . グラフ \(G\) が \(2k (k \ge 1)\) に対して孤立隣接条件を満たすのであれば、ファミリ \(F_{G,k}\) は自己回避的である。

証明. (省略) ∎

我々はすでに \(k=\Omega(\log n)\) の孤立隣接条件を満たす明示的な二部グラフを構築する方法を知っている: これはセクション 11.3.2 で構築された二部ぺーリーグラフ \(G_n\) である。

\(\mathcal{F}_{G_n,k}\) と一致する最小項集合を持つ関数は、セクション 10.6.2 で導入された単調ブール関数 \({\rm PALEY}(n,k)\) である。ここで我々は関数が単調回路には難しいことが証明された。セクション 15.2.2 では関数が小さな単調式では実現できないことを証明した。

ここでこの関数が単調スパンプログラムにとっても難しいことを示すことができる: 定理 11.9 で与えられた境界は \(G_n\) が \(2k\) の孤立隣接条件を満たしていることを意味し、それは \(2k4^k \lt \sqrt{n}\) の限りであり、したがって \(k=\Omega(\log n)\) についても同様である。補題 16.10 を定理 16.8 と併せて適用すると \({\rm PALEY}(n,k)\) を計算する任意の単調スパンプログラムは少なくとも \(|\mathcal{F}_{G_n,k}|=\left(\begin{array}{c}n\\k\end{array}\right)=n^{\Omega(\log n)}\) のサイズを持たなければならない。

Babai, Gál および Wigderson (1999) が定式化したスパンプログラムに関する 4 つの未解決問題でこの章を終える:

1. 指数サイズの自己回避スペルナーシステムは存在するか?
2. 指数サイズの単調回路を必要とする多項式サイズの単調スパンプログラムを許容する関数は存在するか?
3. 超多項式サイズの単調スパンプログラムを必要とする多項式サイズの単調回路を許容する関数は存在するか?
4. 単調スパンプログラムは非単調スパンプログラムよりどれほど弱いか?

演習

参考文献

1. Jukna, Dr. Stasys, Span Program. In Extremal Combinatorics. page 205-218. Springer 2001
2. M. Karchmer, A. Wigderson. On Span Programs, Proc. 8-th Annual Structure in Complexity Theory Conference, San Diego, California, 18-21 May 1993. IEEE Computer Society Press, pp. 102-111. (日本語訳)