Processing math: 0%

2020年3月11日水曜日

小さい体上の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^nx\mathbb{F}_q^nから一様ランダムにとってきたベクトルとします。

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

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

補題.
P:\mathbb{F}_2 \to \mathbb{F}_2d次多項式であり、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).
の形で書くことができる。ここで Rk-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
出力: Gk-クリークを部分グラフとして含むなら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}_kG内でクリークをなす辺 \{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).

講義資料をNotionで書いてみた

 プログラミング応用という名前の講義を受け持っており, そこで組合せ最適化のベーシックな話題とそのPythonでの実装を教えているのですが, 資料をNotionで書いてみました. 講義資料をNotionで公開しているのでアルゴリズムの基礎とかNP困難性とかを勉強したい人はどう...