EC25_nagase

25. Randomized Algorithms
B4 永瀬高志
25.1 Zeroes of multivariate polynomials


多変数多項式 f ( x1 ,...., xn ) が常に０かどうかを
調べたい
片っぱしから調べるとexponentialな時間がか
かってしまう
25.1 Zeroes of multivariate polynomials

ランダムアルゴリズム
ランダムな値を各変数に入れて、結果が０でないな
ら、 f  0 という結果を返す
結果が０ならば、try again
これを何度か繰り返し、毎回 f  0 ならば
f  0という結果を返す
変数の取りうる範囲が｛0,1,…,N-1｝のとき、errorに
なる可能性は０ではない。
・しかし、Nが十分に大きいとき限りなく可能性は０に
なる。 ←このことを証明していく
25.1 Zeroes of multivariate polynomials

その前に
関数
f ( x1 ,...., xn ) の次数と全次数
f  x x2  x1 x x
3
1
2
2
2
3
このとき次数は３
全次数は５
25.1 Zeroes of multivariate polynomials

Lemma 25.1
０関数でない関数 f ( x1 ,...., xn ) の全次数をd、体を F とし、 S  F
n
を満たすSをとってきたとき、 f (a1,...., an )  0 を満たす (a1 ,...., an )  S が
n
n1
少なくとも | S | d・ | S | 個ある
| S |n
が
a
の取りうる全体なので、 f (a1 ,...., an )  0 となる点が最大で d・
であることを言えばよい
| S |n1
25.1 Zeroes of multivariate polynomials

Lemma 25.1
０関数でない関数 f ( x1 ,...., xn ) の全次数をd、体を F とし、 S  F
n
を満たすSをとってきたとき、 f (a1,...., an )  0 を満たす (a1 ,...., an )  S が
n
n1
少なくとも | S | d・ | S | 個ある
証明
数学的帰納法で証明を行う
n=1のとき、
例
f 0
の解は次数dを超えないので、成り立つ。
f ( x)  b0 x  b1 x
d
d 1
 ....  0
25.1 Zeroes of multivariate polynomials

Lemma 25.1
０関数でない関数 f ( x1 ,...., xn ) の全次数をd、体を F とし、 S  F
n
を満たすSをとってきたとき、 f (a1,...., an )  0 を満たす (a1 ,...., an )  S が
n
n1
少なくとも | S | d・ | S | 個ある
n  2 のとき、関数fを次のようにおく。
f  f 0  f1 xn  f 2 xn2  ...  f t xnt
f 0 ,..., ft はn-1変数で、引数に x ,..., x をとる。また、 f t は常に０でなく、t
1
n1
d
とする。
ここで、 f (a, b) 
以下、
f0 (a)  f1 (a)b  f 2 (a)b 2  ...  ft (a)bt とし、
f (a, b)  0 を満たす点 (a, b)  S n1  S が、最大いくつあるかを考える。
25.1 Zeroes of multivariate polynomials
１． ft (a)  0 の場合
f t は常に０ではなく、全次数は d  t 以下であるn-1変数の関数であるから、とりう
る a のあたいは高々(d  t ) | S |n2 通りである。さらに xn の値の選び方は | S |通り
あるので、f (a, b)  0 となる(a, b) の選び方は最大で (d  t ) | S |n1通り
f (a, b)  f0 (a)  f1 (a)b  f 2 (a)b 2  ...  ft (a)bt
25.1 Zeroes of multivariate polynomials
２． ft (a)  0 の場合
a を ft (a)  0 を満たす点に固定して考える。このとき f (a, b) は変数 b の多項式と
考えることができる。いま、b の最大次数はtなので、f (a, b) となるbは最大でt通り。
n 1
また、a の選び方は最大で| S |
は最大で t | S |n1 通り
通りあるので、
f (a, b)  0 となる (a, b) の選び方
f (a, b)  f0 (a)  f1 (a)b  f 2 (a)b 2  ...  ft (a)bt
１．２．よりｆ＝０となる点 x1 ,..., xn1 は最大で
(d  t ) | S |n1 t・ | S |n1  d・ | S |n1 通り存在すること
25.1 Zeroes of multivariate polynomials

Lemma 25.1
関数 f ( x1 ,...., xn )の全次数をd、体を F とし、S  F
n
を満たすSをとってきたとき、 f (a1,...., an )  0 を満たす (a1 ,...., an )  S が
n
n1
少なくとも | S | d・ | S | 個ある
もし、関数 f ( x1 ,...., xn ) の次数がdだとすると、全次数は最大でdnになってしまう。
| S | n の場合、このLemma 25.1は全く役に立たない
25.1 Zeroes of multivariate polynomials

Lemma 25.2
０関数でない関数 f ( x1 ,...., xn ) の次数をd、体を F とし、S  F
n
を満たすSをとってきたとき、 f (a1,...., an )  0 を満たす (a1 ,...., an )  S が
n
少なくとも (| S | d ) 個ある
証明数学的機能法で行う
n=1 のとき f は常に０の関数ではなく、次数はdなので、これを満たす。
n>1 のとき (a1,..., an )  F は f (a1 ,...., an )  0 を満たす点とする。
25.1 Zeroes of multivariate polynomials
次のような関数を考える
f 0 ( x1 ,...., xn1 )  f ( x1 ,..., xn1 , an )
f1 ( xn )  f (a1 ,..., an1 , xn )
f 0 はn-1変数の常に０ではない関数なので、数学的帰納法の仮定より、
f 0 ( x1 ,..., xn1 )  0 を満たす点は少なくとも (| S | d )n1 個ある。
f1 も同様に１変数の常に０ではない関数なので、 f1  0 となる x は
n
| S |  d個ある。
よって０でない点は S n に少なくとも (| S | d )
n1
(| S | d )  (| S | d )n点ある。
25.1 Zeroes of multivariate polynomials

Lemma 25.2
０関数でない関数 f ( x1 ,...., xn ) の次数をd、体を F とし、S  F
n
を満たすSをとってきたとき、 f (a1,...., an )  0 を満たす (a1 ,...., an )  S が
n
少なくとも (| S | d ) 個ある
このことから次のことが言える

Corollary 25.3
S  F を、要素を d  1以上もつものとする。０関数でない、次数dのあらゆ
n
る関数は、S において０でない点をもつ。
25.1 Zeroes of multivariate polynomials

Lemma 25.2
０関数でない関数 f ( x1 ,...., xn ) の次数をd、体を F とし、S  F
n
を満たすSをとってきたとき、 f (a1,...., an )  0 を満たす (a1 ,...., an )  S が
n
少なくとも (| S | d ) 個ある
このことから次のことが言える

Corollary 25.4
f ( x1 ,...., xn ) を次数dの０関数でない関数とする。ある S  F において
ランダムに値 r1 ,..., rn をとったとき、次のことが言える。

d 
Pr ob( f (r1 ,..., rn )  0)  1 

 | S |
n
25.1 Zeroes of multivariate polynomials

Corollary 25.4
f ( x1 ,...., xn ) を次数dの０関数でない関数とする。ある S  F において
ランダムに値 r1 ,..., rn をとったとき、次のことが言える。

d 
Pr ob( f (r1 ,..., rn )  0)  1 

 | S |
今、Sが十分大きいときを考えるので、| S
n
| 2dn
とする。
n
1 

Pr ob( f (r1 ,..., rn )  0)  1  1    1 / 2
 2n 
25.2 Verifying the equality of long strings
Bob
Alice
a  a・・・
0
通信
an1
b  b・・・
0
bn1
ai , bi {0,1}
nビットの通信で同じであることを調べられる
しかし、なるべく少ない通信で一致することを調べたい。
ランダムアルゴリズムを使えば高い確率（少なくとも 1  n 1 ）で判別でき、およ
そ O(log n) ビットの通信で行える
25.2 Verifying the equality of long strings
方法
2
2
p個の要素を持つ Fp における関数を考える（pはn  p  2n を満たす素数）
A( x)  a0  a1x  ...  an1x n1 (mod p),
B( x)  b0  b1x  ...  bn1x n1 (mod p).
Aliceはランダムな値 r  Fp と A(r ) をBobに送り、Bobは A(r )  B ( r ) なら１を
A(r )  B(r ) なら０をAliceに送る。
このときの通信量は 1  2 log p  O(log n)
A( x), B ( x) は最大でも次数はn-1なので、A( x)  B( x) となる点も高々n-1となる。
よって、
n 1 n 1 1
Pr ob( A(r )  B(r )) 


|F|
p
n
25.3 The equivalence of branching programs
次のようなグラフを考える。
・それぞれの矢印に変数を割り当てる。
・スタート、ゴールとなる頂点がそれぞれ一つずつあり、また、各頂点から出る矢印
は最大で２本。
・２本矢印が出ている場合は一方に xi もう一方に xi を割り当てる。
y
x
スタート
z
y
y
ゴール
z
x
y
x yz
25.3 The equivalence of branching programs
このようなグラフPとQがあったとき、P(a)  Q(a) , a {0,1}n を調べたい。
グラフPを関数 f p に変換する。
y
グラフP
スタート
x
z
y
y
ゴール
z
x
y
f p  xyz  x(1  y )(1  z )  (1  x) y (1  z )  (1  x)(1  y ) z
25.3 The equivalence of branching programs
関数 f p への変換方法
１．スタート頂点の値を１とする。
２．辺の値が xi なら 1  xi にする。
３．各頂点の値を、『入ってくる矢印の値×矢印の根元の頂点の値』の和にする
x
x
1
1 xx
y
xy+(1-x)(1-y)
z
1 yy
1  yy
1z  z
z{xy+(1-x)(1-y)} +
(1-z){x(1-y)+(1-x)y}
y
1-x
x(1-y)+(1-x)y
時間は
| E |  | V | 1
25.3 The equivalence of branching programs

Corollary 25.4
f ( x1 ,...., xn ) を次数dの０関数でない関数とする。ある S  F において
ランダムに値 r1 ,..., rn をとったとき、次のことが言える。

d 
Pr ob( f (r1 ,..., rn )  0)  1 

 | S |
n
問題グラフPとQがあったとき、 P(a)  Q(a) , a {0,1}n を調べたい。
グラフP,Qを関数 f P , fQ に変換して調べるとき、errorが起こる確率を考える。
Corollary 25.4より、| S | 2n とすると、
n

1 
Pr ob( P(r )  Q(r ))  1  1 
 ~ 1  e1/ 2  1 / 2
 | S |
25.4 A min-cut algorithm


カットとは、グラフの頂点を2つの部分集合に分割することで、最小カット
はそのために最小の数の辺を切るものである。
この最小カットをランダムアルゴリズムで求めるとき、以下の操作を行う
ランダムに辺を選び、その辺が結ぶ２頂点をくっつける。これを頂点が２つに
なるまで繰り返す
25.4 A min-cut algorithm
『この操作によってmin-cutのサイズが減ることはない』ということが知られてい
るので、これを繰り返すことによって得られる結果はmin-cutである可能性が
ある。その確率について考える
補題グラフ G  (V , E ) にはn個の頂点があり、kより小さいcutは存在しないと
すると、辺は最低でもkn/2存在する
証明
頂点 v V の次数は d (v)  k で、Theorem 1.7より
よって 2 | E | k・ | V | kn なので | E | kn / 2

vV
d (v)  2 | E |
25.4 A min-cut algorithm
グラフGの最小カットをCとし、そのサイズをkとする。
また、Ai を『i番目のステップでCに含まれる辺を消さない』という事象とする。
このとき
Pr ob(アルゴリズムがCを結果として出す)  Pr ob( A1  A2  ....  An2 )
|C |
k
2


また、 | E |  kn  n
 
 2
であるから、 Pr ob( A1 )  1 
2
n
25.4 A min-cut algorithm
次に Pr ob( A2 |
A1 ) を考える。
A1 の後、n-1頂点があるので、少なくともk (n  1) / 2 個の辺がある。
よって、
Pr ob( A2 | A1 )  1 
2
n 1
同様に、Ai のときを考えると
i 1


2
Pr ob Ai |  Aj   1 
n  i 1
j 1


25.4 A min-cut algorithm
よって
 n2 
Pr ob  Aj   Pr ob( A1・) Pr ob( A2 | A1・・・
)
 j 1 
n2
2 

  1 

n

i

1

i 1 
3

j n
n 3


Pr ob An2 |  Aj 
j 1


j2
2

j
n(n  1)
2
つまり、このアルゴリズム１回で正しい解を見つける確率が少なくとも n( n  1)
25.4 A min-cut algorithm
もし、このアルゴリズムを n 2 / 2 回行ったとする。
そのとき、errorとなる確率は高々
(1  2 / n )
2 n2 / 2
 e1  0.37
さらに繰り返す回数を増やすことでerrorが起こる確率を減らすことができる。

Download Report