一般誕生日問題 k-sum を解くための k-tree アルゴリズム

Table of Contents

はじめに

この記事では、一般化された誕生日問題である k-sum 問題を解くための k-tree アルゴリズムを紹介します。まず、この記事で多用する排他的論理和の性質と記号の定義を挙げ、 $k=4$ のときの k-sum 問題と k-tree アルゴリズムについて述べます。最後に、一般的な k-tree アルゴリズムについて述べます。

排他的論理和の性質と記号の定義

$a\oplus b = 0$ ならば $a = b$
$a \oplus b \oplus ...$ のように複数個の排他的論理和をとる場合、 $a, b, ...$ の中で $1$ であるものの個数が奇数個ならば結果は $1$ 、偶数個ならば $0$ となる。
$list S,listT$ に対し $S \triangleright\triangleleft T$ は $S,T$ の共通要素から成る $list$ である。
$low_l(x)$ は $x$ の最下位 $l$ ビットとする。
$L_1\triangleright \triangleleft_l L_2$ は $L_1 \times L_2$ から最下位 $l$ ビットが一致する全てのペアを含む $list$ である。
$x_1 \oplus x_2 = x_3 \oplus x_4$ ならば $x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0$

k=4 の k-sum 問題

$x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0$ となるような $x_1,x_2,x_3,x_4$ の $list$ を見つける。

k-tree アルゴリズムによる解法

$L_1,L_2,L_3,L_4$ は要素をそれぞれ $2^l$ 個含む $list$ とする。

$low_l(x_1 \oplus x_2)=0$ となるような $x_1 \oplus x_2$ の $list$ である $L_{12}$ を作る。同様に $low_l(x_3 \oplus x_4)=0$ となるような $x_3 \oplus x_4$ の $list$ である $L_{34}$ を作る。

性質

$x_1 \oplus x_2 = x_3 \oplus x_4$ ならば $x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0$

より

$L_{12}$ と $L_{34}$ から $x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0$ となるような $x_1,x_2,x_3,x_4$ の $list$ を見つけられる。

計算量について

$low_l(x_1 \oplus x_2)=0$ となるような確率は $1/2^l$

E[|L_{12}|]=|L_1|\times|L_2|\div2^l=2^{2l}\div2^l=2^l

同様に $L_{34}$ のサイズも $2^l$

性質

$low_l(x_1 \oplus x_2)=0$ かつ $low_l(x_3 \oplus x_4)=0$ ならば　
$low_l(x_1 \oplus x_2 \oplus x_3 \oplus x_4)=0$ となる確率は $2^l/2^n$

より、
$L_{12}$ と $L_{34}$ の共通要素の個数は $|L_{12}|\times|L_{34}|\div 2^{n-l}$ と見積もれる。

ここで $|L_{12}|\times|L_{34}|\div 2^{n-l}= 2^l ×2^l \div 2^{n-l} =2^{3l-n}$ より
$l \ge n / 3$ (逆だと確率が $1$ を超えてしまうから)

手順の始まりに $l = n / 3$ とすると、 $k=4$ の birthday problem を自明でない確率で解けることになる。

一般的な k に対する k-tree アルゴリズム

k が 2 の累乗の時
$k=4$ のアルゴリズムで用いた、 $list$ の分割を $\log_2k$ 回行って同様の操作を行えば良い。(以下、 $\log_2k=lgk$ と表す。) $O(k・2^{n/(1+lgk)})$ 時間で解ける。
k が 2 の累乗ではない時
$k' = 2^{\lfloor lg k \rfloor}$ として $list$ 分割を行えば良い。ただし、 $k = 2^i+j$ の場合は、 $k = 2^i$ の場合よりも基本的に速く解くことは出来ない。