25. Randomized Algorithms B4　永瀬　高志

25.1 Zeroes of multivariate polynomials 多変数多項式　　　　　　　　　が常に０かどうかを調べたい 片っぱしから調べるとexponentialな時間がかかってしまう

25.1 Zeroes of multivariate polynomials ランダムアルゴリズム 　ランダムな値を各変数に入れて、結果が０でないなら、　　　　　という結果を返す 　結果が０ならば、try again　 　これを何度か繰り返し、毎回　　　　　ならば 　　　　　という結果を返す 　変数の取りうる範囲が｛0,1,…,N-1｝のとき、errorになる可能性は０ではない。 ・　しかし、Nが十分に大きいとき限りなく可能性は０になる。　←このことを証明していく

25.1 Zeroes of multivariate polynomials その前に 　関数　　　　　　　　　　　の次数と全次数 　　　　　　　　　　　　　　　　　　　このとき次数は３ 　　　　　　　　　　　　　　　　　　　　　全次数は５

25.1 Zeroes of multivariate polynomials Lemma 25.1 ０関数でない関数　　　　　　　の全次数をd、体を　　とし、　　　　　　　　　　　　　　　 を満たすSをとってきたとき、　　　　　　　　　 を満たす が 少なくとも　　　　　　　　　　個ある 　　　　　が の取りうる全体なので、　　　　　　　　　　　となる点が最大で であることを言えばよい

25.1 Zeroes of multivariate polynomials Lemma 25.1 ０関数でない関数　　　　　　　の全次数をd、体を　　とし、　　　　　　　　　　　　　　　 を満たすSをとってきたとき、　　　　　　　　　 を満たす が 少なくとも　　　　　　　　　　個ある 証明　　数学的帰納法で証明を行う 　n=1のとき、　　　　　　の解は次数dを超えないので、成り立つ。 例

25.1 Zeroes of multivariate polynomials Lemma 25.1 ０関数でない関数　　　　　　　の全次数をd、体を　　とし、　　　　　　　　　　　　　　　 を満たすSをとってきたとき、　　　　　　　　　 を満たす が 少なくとも　　　　　　　　　　個ある 　　　　のとき、関数fを次のようにおく。 　　　　　　はn-1変数で、引数に　　　　　　 をとる。また、　　は常に０でなく、 とする。 ここで、　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　とし、 以下、　　　　　　　　を満たす点　　　　　　　　　　　が、最大いくつあるかを考える。　　　　　　

25.1 Zeroes of multivariate polynomials 　　　　　の場合 　　　　は常に０ではなく、全次数は 以下であるn-1変数の関数であるから、とりうる のあたいは高々 通りである。さらに の値の選び方は 通りあるので、 となる の選び方は最大で 通り

25.1 Zeroes of multivariate polynomials ２．　　　　　　の場合 　 を　　　　　　　を満たす点に固定して考える。このとき　　　　　は変数 の多項式と 　考えることができる。いま、 の最大次数はtなので、　　　　　となるbは最大でt通り。 　また、 の選び方は最大で 通りあるので、 となる の選び方は最大で 通り １．２．よりｆ＝０となる点　　　　　　　は最大で 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　通り存在すること

25.1 Zeroes of multivariate polynomials Lemma 25.1 関数　　　　　　　の全次数をd、体を　　とし、　　　　　　　　　　　　　　　 を満たすSをとってきたとき、　　　　　　　　　 を満たす が 少なくとも　　　　　　　　　　個ある もし、関数　　　　　　　　の次数がdだとすると、全次数は最大でdnになってしまう。 　　　　　　の場合、このLemma 25.1は全く役に立たない　　　

25.1 Zeroes of multivariate polynomials Lemma 25.2 ０関数でない関数　　　　　　　の次数をd、体を　　とし、　　　　　　　　　　　　　　　 を満たすSをとってきたとき、　　　　　　　　　 を満たす が 少なくとも　　　　　　　個ある 証明　数学的機能法で行う n=1 のとき　は常に０の関数ではなく、次数はdなので、これを満たす。 n>1 のとき　　　　　　　　　は　　　　　　　　　　　を満たす点とする。

25.1 Zeroes of multivariate polynomials 次のような関数を考える 　　　はn-1変数の常に０ではない関数なので、数学的帰納法の仮定より、 　　　　　　　　　　　　　　　　　　を満たす点は少なくとも　　　　　　　　　　個ある。 　　　も同様に１変数の常に０ではない関数なので、　　　　となる　　 は 　　　　　　　個ある。 よって０でない点は　　に少なくとも　　　　　　　　　　　　　　　　　　　　点ある。

25.1 Zeroes of multivariate polynomials Lemma 25.2 ０関数でない関数　　　　　　　の次数をd、体を　　とし、　　　　　　　　　　　　　　　 を満たすSをとってきたとき、　　　　　　　　　 を満たす が 少なくとも　　　　　　　個ある このことから次のことが言える Corollary 25.3 　　　　を、要素を 以上もつものとする。０関数でない、次数dのあらゆる関数は、　　において０でない点をもつ。　　　　

25.1 Zeroes of multivariate polynomials Lemma 25.2 ０関数でない関数　　　　　　　の次数をd、体を　　とし、　　　　　　　　　　　　　　　 を満たすSをとってきたとき、　　　　　　　　　 を満たす が 少なくとも　　　　　　　個ある このことから次のことが言える Corollary 25.4 　　 を次数dの０関数でない関数とする。ある　　　　　において ランダムに値　　　　　　 をとったとき、次のことが言える。

25.1 Zeroes of multivariate polynomials Corollary 25.4 　　 を次数dの０関数でない関数とする。ある　　　　　において ランダムに値　　　　　　 をとったとき、次のことが言える。 今、Sが十分大きいときを考えるので、　　　　　　　　とする。

25.2 Verifying the equality of long strings Bob Alice 通信 nビットの通信で同じであることを調べられる しかし、なるべく少ない通信で一致することを調べたい。 　ランダムアルゴリズムを使えば高い確率（少なくとも ）で判別でき、およそ　　　　　　ビットの通信で行える

25.2 Verifying the equality of long strings 方法 p個の要素を持つ　　 における関数を考える（pは　　　　　　　　　を満たす素数） Aliceはランダムな値 と　　　 をBobに送り、Bobは　　　　　　　　　なら１を 　　　　　　　　　なら０をAliceに送る。 このときの通信量は　　　　　　　　　　　　　　　 　　　　　　　は最大でも次数はn-1なので、　　　　　　　　 となる点も高々n-1となる。 よって、

25.3 The equivalence of branching programs 次のようなグラフを考える。 ・それぞれの矢印に変数を割り当てる。 ・スタート、ゴールとなる頂点がそれぞれ一つずつあり、また、各頂点から出る矢印は最大で２本。 ・２本矢印が出ている場合は一方に　 もう一方に　 を割り当てる。 ゴール スタート

25.3 The equivalence of branching programs このようなグラフPとQがあったとき、 を調べたい。 グラフPを関数　　に変換する。 グラフP ゴール スタート

25.3 The equivalence of branching programs 関数　　への変換方法 １．スタート頂点の値を１とする。 ２．辺の値が　　なら　　　　にする。 ３．各頂点の値を、『入ってくる矢印の値×矢印の根元の頂点の値』の和にする x xy+(1-x)(1-y) z{xy+(1-x)(1-y)} + (1-z){x(1-y)+(1-x)y} 1 1-x x(1-y)+(1-x)y 時間は

25.3 The equivalence of branching programs Corollary 25.4 　　 を次数dの０関数でない関数とする。ある　　　　　において ランダムに値　　　　　　 をとったとき、次のことが言える。 問題　グラフPとQがあったとき、 を調べたい。 グラフP,Qを関数　　　　　に変換して調べるとき、errorが起こる確率を考える。 Corollary 25.4より、　　　　　　とすると、

25.4 A min-cut algorithm カットとは、グラフの頂点を2つの部分集合に分割することで、最小カットはそのために最小の数の辺を切るものである。 この最小カットをランダムアルゴリズムで求めるとき、以下の操作を行う ランダムに辺を選び、その辺が結ぶ２頂点をくっつける。これを頂点が２つになるまで繰り返す

25.4 A min-cut algorithm 　　『この操作によってmin-cutのサイズが減ることはない』ということが知られているので、これを繰り返すことによって得られる結果はmin-cutである可能性がある。その確率について考える 補題　グラフ　　　　　　　　にはn個の頂点があり、kより小さいcutは存在しないと 　　　　すると、辺は最低でもkn/2存在する 証明 頂点　　　　　の次数は　　　　　　　で、Theorem 1.7より よって　　　　　　　　　　　　　　なので　　　　　　　　　　　　

25.4 A min-cut algorithm グラフGの最小カットをCとし、そのサイズをkとする。 また、　 を『i番目のステップでCに含まれる辺を消さない』という事象とする。 このとき 　　　　 アルゴリズムがCを結果として出す また、 であるから、

25.4 A min-cut algorithm 次に を考える。 の後、n-1頂点があるので、少なくとも 個の辺がある。 よって、 次に　　　　　　　　　　を考える。 　　の後、n-1頂点があるので、少なくとも　　　　　　　個の辺がある。 よって、 同様に、　　のときを考えると

25.4 A min-cut algorithm よって つまり、このアルゴリズム１回で正しい解を見つける確率が少なくとも

25.4 A min-cut algorithm もし、このアルゴリズムを 回行ったとする。 そのとき、errorとなる確率は高々 もし、このアルゴリズムを　　　　 回行ったとする。 そのとき、errorとなる確率は高々 さらに繰り返す回数を増やすことでerrorが起こる確率を減らすことができる。