Sept. 24, 2015@ELC秋学校(岐阜)Exploring theLimits ofComputation

乱択の技法
3. 今後の課題: BPP=P?

来嶋秀治
九州大学 大学院システム情報科学研究院

BPP (Bounded-Error Probabilistic Polynomial-Time)
言語𝐿がBPP 
多項式時間で停止する
確率的 Turing Machineが存在し，以下の条件を満たす．
𝑥 ∈ 𝐿なら確率2/3以上で受理．
𝑥 ∉ 𝐿なら確率1/3以下で受理．

ACCEPT REJECT
≥ 2/3
≤ 1/3
真の解: YES
≤ 1/3
≥ 2/3
真の回: NO2

BPL (Bounded-Error Probabilistic L)
言語𝐿がBPL 
入力サイズ𝑛の対数領域を使用する
確率的 Turing Machineが存在し，以下の条件を満たす．
𝑥 ∈ 𝐿なら確率2/3以上で受理．
𝑥 ∉ 𝐿なら確率1/3以下で受理．

ACCEPT REJECT≥ 2/3≤ 1/3真の解: YES
≤ 1/3
≥ 2/3
真の回: NO3

乱択の威力3.1. ストリーム中の頻出アイテム検知
緒方 正虎, 山内 由紀子, 来嶋 秀治, 山下 雅史
九州大学: “頻出度”パラメータ

ストリームデータ中の頻出アイテム検知

問題: 頻出アイテム検知

5

: アイテム集合(有限)Input: (0,1) x =(x1,…,xN) N (順々に)Find: all s  s.t. f(s)  N

但し f(s) は s が x 中で出現した回数

事前には、N (or log Nの近似値)もわからない。

例1. 1日のPOSデータ(@果物屋) ={,,, …,}
x=,,,,,,,,,,, ….
例. 1日のアクセスIPアドレス
  {0.0.0.0,…,255.255.255.255}
x = 123.45.67.89, 111.11.1.1., 123.45,67,89, 122.122.12.12…
would like to find items appearing w/ frequency more than =1% of N.

6

頻出アイテム検知の領域複雑度
定理 [Karp, Shenker, Papadimitriou ‘03]
頻出アイテム検知を厳密に行うには，
(|| log (N/||)) bits が必要．
(N >> || >> 1/ とする)
定理 [Karp, Shenker, Papadimitriou ‘03]

決定的

頻出アイテム検知に対するO((1/) log N) bits の偽陽性(近似)アルゴリズムが存在．
(N >> || >> 1/ とする)
o(log N) bitsアルゴリズム？
 e.g. O(log log N) bits?

単純化: o(log N) bitsで要素数を数えられるか？
事前には、N (or log Nの近似値)もわからない。

問題: 要素数え上げ
Input: x = (a,…,a) N (順々に)Find: N

アルゴリズム: 数え上げ
0. Set n:= 0.
1. Read an input. If no more input, goto 3.
2. n++, Goto 1.
3. Output n (as N = n).

={x=},,,,……

7単純化: o(log N) bitsで要素数を数えられるか？

問題: 要素数え上げ
Input: x = (a,…,a) N (順々に)Find: N

事前には、N (or log Nの近似値)もわからない。

アルゴリズム: 数え上げ
0. Set n:= 0.
1. Read an input. If no more input, goto 3.
2. n++, Goto 1.
3. Output n (as N = n).
O(log N) bitso(log N) bits近似アルゴリズム？
 e.g. O(log log N) bits?

8単純化: o(log N) bitsで要素数を数えられるか？

問題: 要素数え上げ
Input: x = (a,…,a) N (順々に)Find: N

事前には、N (or log Nの近似値)もわからない。

アルゴリズム:数え上げ
Remark
0.• Setn:= 0. N) bitsで表現可能．
NはO(log1. Readinput. If no more input, goto 3.
 Nan= 1,351,127,649,213
2.• n++,
Goto 1.
Nの近似はO(loglog N) bitsで表現可能
3. Output(as N x= 10n).12 N n1.351
つまり、指数部(=log N)がo(log N) bits領域で近似計算できるか？ということ。

o(log N) bits近似アルゴリズム？
表現はO(logN) bitsで可能
 e.g.logO(loglog N) bits?

9単純化: o(log N) bitsで要素数を数えられるか？

問題: 要素数え上げ
Input: x = (a,…,a) N (順々に)Find: N

事前には、N (or log Nの近似値)もわからない。

アルゴリズム: 数え上げ
0. Set n:=0.
1. Read an input. If no more input, goto 3.
2. n++, Goto 1.
3. Output n (as N = n).
(log N) bits

定理. [Flajolet ‘85, Ogata et al. ‘11]
決定的アルゴリズムでは(log N) bit 必要！

10

11

確率的数え上げ
事前には、N (or log Nの近似値)もわからない。

問題: 要素数え上げ
Input: x = (a,…,a) N (順々に)Find: N

アルゴリズム: 確率的数え上げ
0. Set k:=0.
1. Read an input. If no more input, goto 3.
2. k++, w.p. 1/2k. Goto 1.
3. Output k (as N  2k).

={x=},,,,……

12

確率的数え上げ

問題: 要素数え上げ
Input: x = (a,…,a) N (順々に)Find: N

事前には、N (or log Nの近似値)もわからない。

 key point“w.p. 1/2k ” using
O(log K) bits on PTM.

アルゴリズム: 確率的数え上げ
0. Set k:=0.
1. Read an input. If no more input, goto 3.
2. k++, w.p. 1/2k. Goto 1.
3. Output k (as N  2k).
O(log log N) bits

Thm. [Morris ‘78, Flajolet ‘85]
E[2k]  N+1because
N  1+2+4+8+16+…+2k

13

確率的数え上げ(改良型)
事前には、

問題: 要素数え上げ b
N (or log Nの近似値)も(直感的に) “l” (< 2N ) は仮数部分を表す．
Input: x = (a,…,a)  (順々に)わからない。
kで)捕まえておく.
i.e.,
各ひつじを牧場“l”に(確率1/2
Find: N
アルゴリズム: 確率的数え上げ(改良型)
l0. Set k:=0, l:=0.
1. Read an input. If no more input, goto 4.
2. l++, w.p. 1/2k.
𝑏𝑏2−2b
3. If l==2 , k++, and set l := l’ w.p.
∙ 2 . Goto 1.
𝑙′
4. Output l and k (as N  l *2k ).
各ひつじは，k反復目の時，確率1/2kで(牧場“l”に)残っている．
Thm. [Ogata, Yamauchi, K., Yamashita ‘11]jで捕まったひつじはなぜなら“exponent”=jの時捕まった確率1/2“exponent”=k(k > j)の時，確率1/2k-jで牧場に残っている．
kE[l*2 ]  N.
 Pr[ひつじ in l] = 1/2j * 1/2k-j = 1/2k.

14

確率的数え上げ(改良型)

問題: 要素数え上げ
Input: x = (a,…,a) N (順々に)Find: N

事前には、N (or log Nの近似値)もわからない。

アルゴリズム: 確率的数え上げ(改良型)
0. Set k:=0, l:=0.
1. Read an input. If no more input, goto 4.
2. l++, w.p. 1/2k.
𝑏𝑏2−2b
3. If l==2 , k++, and set l := l’ w.p.
∙ 2 . Goto 1.
𝑙′
4. Output l and k (as N  l *2k ).
O(log log N) bits
Thm. [Ogata, Yamauchi, K., Yamashita ‘11]
E[l*2k]  N.

“改良型” を使うと、頻出アイテム検知も可能．(詳細略)ストリームデータ中の頻出アイテム検知

問題: 頻出アイテム検知
Input: (0,1) x =(x1,…,xN) N (順々に)Find: all s  s.t. f(s)  N

但し f(s) は s が x 中で出現した回数

o(log N) bitsアルゴリズム？
 e.g. O(log log N) bits?

15

事前には、N (or log Nの近似値)もわからない。

16

ストリームデータ中の頻出アイテム検知

問題: 頻出アイテム検知
Input: (0,1) x =(x1,…,xN) N (順々に)

事前には、N (or log Nの近似値)もわからない。

Find: all s  s.t. f(s)  N

但し f(s) は s が x 中で出現した回数

Thm. [Ogata, Yamauchi, K., Yamashita ‘11]
O(log log N) bits 領域の乱択近似アルゴリズムが存在.
詳細略o(log N) bitsアルゴリズム？
 e.g. O(log log N) bits?

3.2. Probabilistic Counting

18

確率的数え上げ
事前には、N (or log Nの近似値)もわからない。

問題: 要素数え上げ
Input: x = (a,…,a) N (順々に)Find: N

アルゴリズム: 確率的数え上げ
0. Set k:=0.
1. Read an input. If no more input, goto 3.
2. k++, w.p. 1/2k. Goto 1.
3. Output k (as N  2k).

={x=},,,,……

19

Probabilistic Counting by Morris

Prob. Count. by Morris.
0. Set “exponent” ℎ ≔ 0.
1. Read an input if exists, otherwise goto 3.
2. Increment ℎ by one w/ porbability

1. Goto 1.
2ℎ

3. Output ℎ (as log 𝑛).

R. Morris, Counting large numbers of events in small registers,Communications of the ACM, 21(1978), 840–842.

Probabilistic Counting by Karpinski & Verbeek

Prob. Count. by Karpinski & Verbeek
0. Set “exponent” ℎ ≔ 0. Set TMP ≔ 0.
1. Read an input if exists, otherwise goto 6.
2. Generate a random bit 𝑟 ∈ {0,1}.
3. If 𝑟 = 1 then TMP + +,4. else TMP ≔ 0.
5. If TMP > ℎ, then ℎ ≔ TMP (infact, just ℎ + +).
6. Return ℎ (as log 𝑛).

M. Karpinski and R. Verbeek. On the Monte Carlo SpaceConstructible Functions and Separation Results for Probabilistic
Complexity Classes. Information and Computation, 75:178-189, 1987.

20

Probabilistic Counting by Uehara

Prob. Count. by Uehara
0. Set “exponent” ℎ ≔ 0. Set TMP ≔ 0.
1. Read an input if exists, otherwise goto 8.
2. Set TMP ≔ 0. Set 𝑟 ≔ 1.
3. While(𝑟 = 1){4.
Generate a random bit 𝑟 ∈ {0,1}5.
TMP + + unless 𝑟 = 0.
6. }7. If TMP > ℎ, then ℎ ≔ TMP.
8. Return ℎ (as log 𝑛)

上原隆平. 確率Turing Machineにおける低いレベルの領域強構成可能性について. 情報基礎理論ワークショップ, 1993.

21

log log 𝑛をO(log log log 𝑛)bit計算領域で近似できるか？

(たぶん)未解決問題
log log 𝑛 ∈ BPSPACE(log log log 𝑛)?

期待値の意味では可能．

22

マニアックな話 = 細かい話

3.3. 確率的Turing Machine
決定性TM + {0,1}乱数

24

BPP vs ZPP
多項式時間停止 vs 期待多項式時間

https://en.wikipedia.org/wiki/BPP_%28complexity%29

RP (Randomized Polynomial-Time)
言語𝐿がRP 
多項式時間で停止する
確率的 Turing Machineが存在し，以下の条件を満たす．
𝑥 ∈ 𝐿なら確率1/2以上で受理．
𝑥 ∉ 𝐿なら非受理．

ACCEPT REJECT≥ 1/2≤ 1/2真の解: YES
01
真の回: NO

25

ZPP (Zero-Error Probabilistic Polynomial-Time)
言語𝐿がZPP 
期待値として多項式時間で停止する
確率的 Turing Machineが存在し，以下の条件を満たす．
𝑥 ∈ 𝐿なら確率1で受理．
𝑥 ∉ 𝐿なら確率1で非受理．

ACCEPT REJECT
10真の解: YES
01
真の回: NO命題
ZPP = RP ∩ co-RP

26確率的TMは有限時間停止性に弱い

27

細かい話

命題
確率的TMでは有限時間停止の最適じゃんけんは実装できない．
最適じゃんけん {グー，チョキ，パー}の一様分布．
 つまり，確率1/3は有限時間停止では実装できない．

{1,2,3}上の一様分布の実装1

generate random real 𝜆 ∈ [0,1)28を丁寧に書き下すと．

素直な実装
0. Set 𝑖 = 1.
1. Generate 𝑟𝑖 ∈ {0,1}.
1
2. If 0. 𝑟1 𝑟2 ⋯ 𝑟𝑖 11 ⋯ < then output 1.
3.

3
12
If 0. 𝑟1 𝑟2 ⋯ 𝑟𝑖 00 ⋯ > and 0. 𝑟1 𝑟2 ⋯ 𝑟𝑖 11 ⋯ <332If 0. 𝑟1 𝑟2 ⋯ 𝑟𝑖 11 ⋯ < then output 3.
3

then output 2.

4.
5. Else goto 1.

12

1/3=0.01010....

32/3=0.10101....

たとえば乱数列が0.010101と続くと1か2か定まらない． 有限時間停止しない．．．

29

有限時間停止しないことの証明

 アルゴリズムAは有限時間停止するとして，{0,1}乱数を高々𝑛個生成するものとする．
 この「高々」は「丁度」に置き換えられる．
 例えば，Aで 𝑘 < 𝑛 個の生成で出力される値は，そのあとも(無駄に)𝑛個になるまで乱数を生成して，最初の 𝑘 個だけ使う．
 この時，実現される確率はすべて
13𝑎21の整数倍2𝑛 しかし， = 𝑛 となる𝑎は存在しない．矛盾．

30{1,2,3}上の一様分布の実装2実装 2
1. Generate 𝑟1 ∈ {0,1}, 𝑟2 ∈ {0,1}.
2. If 𝑟1 𝑟2 = 00 then output 1.
3. If 𝑟1 𝑟2 = 01 then output 2.
4. If 𝑟1 𝑟2 = 10 then output 3.
5. Else goto 1.
123

やり直し

00

01

1011

生成する乱数の期待個数．
∞𝑘3
82𝑘=43𝑘=1(幾何分布の期待値より)

実装1と実装2は実は同じ．

31

有理数確率の離散確率変数の生成

命題
確率変数𝑋 ∈ 1,2, … , 𝑛 は細かい点として，𝑏𝑘
ここの値とまず比較する
Pr 𝑋 = 𝑘 =𝑎𝑘のがO lg 𝐴 時間のポイント．とする．𝐴 = gcd(𝑎1 , … , 𝑎𝑛 )とすると，期待値として2 lg 𝐴個のランダムビットを生成して，期待時間 O lg 𝐴 で所望の𝑋が得られる．
1

1

1

2

2

3

やり直し

 [0,1)区間を2 lg 𝐴 分割して，𝑘を適切に割り当てる．
𝐴𝑏𝑎𝑘 𝑘𝑏𝑘=に注意．
𝑎𝑘𝐴 𝐴 ≤ 2 lg 𝐴 ≤ 2𝐴 より，確率1/2以上で割り当てられる．

 あとは幾何分布の期待値と二分探索．

無理数の確率でもうまくいく

命題
確率変数𝑋 ∈ {1, … , 𝑛}の累積分布確率を
𝑘𝐹 𝑘 =Pr 𝑋 = 𝑘𝑖=1とする．任意の𝑘に対して，関数𝐹(𝑘)の2進𝑗桁目の値が𝑔 𝑗 = O (2 − 𝜀)𝑗 で計算できるとき，期待値として高々 2 lg 𝑛 個のランダムビットを生成して，期待時間 O ⌈log 𝑛⌉ +22−𝜀で所望の𝑋が得られる．

32

33

何が問題なの？
generate random real 𝜆 ∈ [0,1) をして，{1, … , 𝑛}に関する単純な二分探索だと，区別をつけるのに時間がかかる場合がある．

一様乱数がここに落ちると困る．

0.1

0.1000000000000001
0.10000000000000001

34

証明の概略
12

(⌈log 𝑛⌉ + 1)-bitの乱数を生成すると確率 以上で確定する．
2𝑛個(以上)に分類されるのに，仕切りは𝑛個．
 二分探索O lg 𝑛 このとき，(⌈log 𝑛⌉ + 1)-bitまで計算すればよい．
(⌈log 𝑛⌉ + 𝑘)-bitの乱数を生成すると確率1 −1 𝑘で確定する．
2

すなわち期待計算時間は∞O ⌈log 𝑛⌉ +𝑗=11𝑔 𝑗𝑗2∞

= O ⌈log 𝑛⌉ +𝑗=12−𝜀22= O ⌈log 𝑛⌉ +2−𝜀𝑗

3.4. 対角線論法と測度

360,1 ℚ : 区間[0,1]の有理数集合
0,1 ℝ : 区間[0,1]の実数集合
命題0,1 ℚ
Pr 𝑋 ∈ 0,1 ℚ ==00,1 ℝ
証明（アイデア）
任意の𝑥 ∈ 0,1 ℚ に対してPr 𝑋 = 𝑥 = 0
有理数は可算無限なので，完全加法性より
Pr 𝑋 ∈ 0,1 ℚ =Pr[𝑋 = 𝑥] =𝑥∈ 0,1 ℚ

0=0𝑥∈ 0,1 ℚ

37

対角線論法 0,1 ℚ ≠ 0,1 ℝ から
0,1 ℚ=00,1 ℝ
は導けるか？
注意: 濃度と測度はちがう。

濃度: 0,1 ℝ = 0,1 ℝ × 0,1 ℝ測度: 0,1 ℝ × 0,1 ℝ 上の直線の面積(確率，測度）は0=>測度の方が概念として “弱い”計算量限界に使いたい！

The endThank you for the attention.