補題 (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).
0 件のコメント:
コメントを投稿