読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

切り分けても切り分けても長方形

前の記事: http://azapen6.hatenablog.com/entry/2012/12/29/053705

今回は引き続いて、乱数を使わないで完全なチェックを求める限りは、どうやっても対象のデータをそのまま送信するのと通信量の意味で差をつけられないことの証明に入ります。前回の最後に書いた

D(\mathrm{EQ}) = n + 1

という式が今回示すべきことです。上界の方は前回簡単に済ませたので、下界の方

D(\mathrm{EQ}) \geq n + 1

をこれから示していきます。

タイトルにある「長方形」は、アリスとボブの間の通信量を考察する上での基本的な道具です。長方形といっても普通の長方形ではありません。それはともかくとして、その「長方形」の数を数えることと、通信量を測ることが実質的に同じであるというのが、今回の話の肝です。さて、「長方形」と通信量が一体どのように結びつくのでしょうか?それはこの先のお楽しみです。

組み合わせ的長方形

今回の話の中心は、既に何度も出てきている「長方形(rectangle)」です。しかし、普通の意味での長方形ではなくて、「組み合わせ的長方形(combinatorial rectangle)」と呼ばれるものです。前回に引き続き、アリスの入力の集合を \mathcal{X}、ボブのそれを \mathcal{Y} とします。このとき、ここで言う「長方形」とは、\mathcal{X} \times \mathcal{Y} の部分集合で、直積の形をしているものを言います。

定義:\mathcal{X} \times \mathcal{Y} の部分集合 R が(組み合わせ的)長方形であるとは、2つの集合 A \subseteq \mathcal{X}, B \subseteq \mathcal{Y} が存在して R = A \times B と書けることを言う。

一体どこが長方形?という感じですが、\mathcal{X} \times \mathcal{Y} の要素を行列に並べたとき、適当に行と列を並び替えれば、普通の意味での長方形になるでしょう。また、定義より明らかに \mathcal{X} \times \mathcal{Y} 自体も長方形です。(これは普通の意味でも長方形ですね。)つまるところは用語を似ているものから流用したというだけで、それ以上の深い意味はありません。

今回の話の中核をなす「長方形」とは、言ってしまえばこの程度のものです。しかし、それが通信量を解析する上で極めて重要な働きをするのです。といったところで本題へと入っていきます。

アリスとボブは長方形に切り分ける

アリスとボブのある時点での通信履歴を v \in \{0,1\}^\ast とするとき、そこに到達し得る入力の全体を R_v で表すことにします。例えば、v = \epsilon のときは、すべての入力から到達するので R_\epsilon = \mathcal{X} \times \mathcal{Y} です。v に対して任意に w を連結した通信履歴 vw は、v の後にしか生成されないので、R_{vw} \subseteq R_v が成り立つことも分かります。すなわち、v が伸びるほど R_v は絞られていくと考えられます。

本節で示すべきことは、R_v の絞られ方が、常に長方形を維持し続けるものであるということです。最初の v = \epsilon の時点で R_v が長方形であることは既に言ったことから明らかです。その後も R_v が長方形であり続けることは、少し考えれば分かります。簡単に言うと、アリスは自分の入力の範囲 \mathcal{X} を絞ることしかできず、ボブもまた \mathcal{Y} を絞ることしかできないために、長方形が崩れないのです。つまり、アリスもボブもそれぞれ入力の表を縦もしくは横に切り分けることしかできないのですね。これでは、切り分けた結果はいつで経っても長方形のままでしょう。あとはこの直感をきちんと証明として書き下すだけです。

補題1: すべての v に対して、R_v は長方形である。

証明は \epsilon を最小元とし、連結によって順序が定まる半順序集合 \{0,1\}^\ast における数学的帰納法によって行います。このような議論に慣れていない方は多いでしょう。この命題の場合、示すべきことは次の2つです。

  • v = \epsilon のとき命題が成り立つことを示す。(基底)
  • v = uw \;(w \in \{0,1\}) に関して、u に関して命題が成り立つと仮定(帰納法の仮定)し、v に関しても成り立つことを示す。

上については既に分かっているので、下についてのみ示します。帰納法の仮定として R_u は長方形とします。また、仮にこれから通信を行うのはアリスであるとします。これは、プロトコルの選択関数について \mathrm{sel}(u) = \mathrm{A} であることを意味します。よって、遷移関数は \mathrm{A} が選ばれます。このとき、w \in \{0,1\} に関して

R_v = R_u \cup \{ (x,y) : \mathrm{A}(x,u) = w \}

が成り立ちます。すなわち、アリスが次に送るビットが w であるような入力 x に該当する部分だけが残るのです。最後の集合を書き換えると

\{ (x,y) : \mathrm{A}(x,u) = w \} = \{ x : \mathrm{A}(x,u) = w \} \times \mathcal{Y}

となります。帰納法の仮定として

R_u = A \times B

と書けることをあわせて、

R_v = (A \cup \{ x : \mathrm{A}(x,u) = w \}) \times B

を得ます。これは長方形です。

ボブに関しても同様です。

以上で証明を終わります。ここまで来ても、だからどうした?という感じですが、実はこれこそが今回最も重要な命題なのです。考えてみてください。プロトコルの最後で関数の値が決まるとき、関数の表の中で R_v は一体どのような性質を持っているかを。

補題2: プロトコル \Pi が終了するときの通信履歴をすべて集めた集合を T とするとき、次が成り立つ。

  1. \bigcup_{v \in T} R_v = R_\epsilon = \mathcal{X} \times \mathcal{Y}
  2. すべての相異なる v, w \in T に関して R_v \cup R_w = \emptyset である。
  3. すべての v \in T との (x,y) \in R_v に対して f(x,y) = z は一定である。

証明に入る前に意味をざっと見ます。1と2は、補題1と合わせると、プロトコルは関数の表を長方形の集合に重複なく分割するということを言っています。3は個別の長方形の中で表の関数値が一定であることを言っています。そこで、次の用語を定義します。

定義: 長方形 R に関して、ある z \in \mathcal{Z} が存在して、すべての (x,y) \in R に関して f(x,y) = z であるとき、R は(f に関する)z-単色(monochromatic)長方形であるという。

これを用いると、補題2は、プロトコル \Pi は関数 f の表を単色長方形の集合に重複なく分割する、と言うことができます。このようにして作られた分割を、プロトコル \Pi が導く単色長方形分割と言います。

それでは、補題2の証明に入りましょう。

1はすべての (x,y) \in \mathcal{X} \times \mathcal{Y} に対してプロトコルが停止することから明らかです。どの (x,y)プロトコルが停止した時点での通信履歴 v = \Pi(x,y) に対して R_v に入っています。

2は入力に対して定まる通信履歴が一意であることから判ります。

3はその時点で関数の値が一つに決まることから判ります。

以上で終わりです。証明というほどのこともありませんでした。

本節の内容は、このように非常に簡単なものでしたが、次節ではそれが通信量と結びつくことが明らかになります。

長方形と通信量

前節で示したプロトコルが導く単色長方形分割とプロトコルの通信量は、次の関係で結びつきます。

補題3: プロトコル \Pi に関して L(\Pi) \leq k(定義は前回を参照)ならば、\Pi が導く単色長方形分割は、高々 2^k 個の単色長方形からなる。逆も正しい。

通信履歴がビット列であることを考えれば、これはほとんど明らかです。というのも、長さが高々 k 以下の通信履歴は高々 2^k 個しかありませんから。長さが k より短く終わった通信履歴はそれ以上続かないので、とりあえず後ろに可能なビット列をつなげて長さを k に揃えてやれば、通信履歴の総数が 2^k 以下であることが判ります。逆の方も簡単に示すことができます。

これより関数の通信複雑さに関して次の事実が得られます。

定理4: 関数 f の表を単色長方形に分割するとき、2^k + 1 個以上の長方形を必要とするならば、D(f) \geq k + 1 である。

証明は背理法によります。もし D(f) \leq k ならば、L(\Pi) \leq k を達成するプロトコルが存在するので、補題3より 2^k 個以下の長方形で単色長方形分割が構成できてしまいます。これで矛盾が導けました。よって D(f) \geq k + 1 です。

通信量の下界を証明するための重要な定理がこうも簡単に出たことに拍子抜けされたでしょうか?しかしながら、理論というものは、そのままでは太刀打ちできない問題という城を解りやすいことの積み重ねで落とそうとするものです。通信複雑性の話を入門編として筆者が選んだ理由はここにあります。「理論は難しくない。少なくともそれが対象とする問題そのものよりは。」

Fooling set 法

関数の表を分割するのに必要な単色長方形の数を数える方法として、fooling set 法というものがあります。これは、長方形の自明な性質を利用するものです。それは次のようなものです。

(x_1, y_1), (x_2, y_2) \in \mathcal{X} \times \mathcal{Y} が同じ単色長方形に含まれるならば、(x_1,y_2), (x_2, y_1) の両方もまた同じ単色長方形に含まれる。すなわち、f(x_1,y_1) = f(x_2,y_2) = z ならば f(x_2,y_1) = f(x_1,y_2) = z である。

もちろん、f(x_1,y_1) \neq f(x_2,y_2) ならば (x_1,y_1), (x_2, y_2) が同じ単色長方形に含まれるわけがないので、その場合は考えないことにします。上の対偶をとると、f(x_1,y_1) = f(x_2,y_2) = z のとき

f(x_2,y_1) \neq z または f(x_1,y_2) \neq z ならば (x_1,y_1), (x_2, y_2) は同じ単色長方形には含まれない

ということが判ります。このような性質を満たす集合をもって、単色長方形の数の下界を示すのが fooling set 法です。

定義: 集合 S \subseteq \mathcal{X} \times \mathcal{Y} が fooling set であるとは、ある z \in \mathcal{Z} が存在して、次を満たすことを言う。

  • すべての (x,y) \in S について f(x,y) = z が成り立つ。
  • すべての (x_1,y_1), (x_2,y_2) \in S について、f(x_1,y_2) \neq z または f(x_2,y_1) \neq z の少なくとも一方が成り立つ。

上の議論より明らかに、fooling set に属するすべての (x,y) は各々別々の単色長方形に属さなければなりません。よって、次のことが言えます。

補題5: 関数 f が個数 2^k 以上の fooling set を持つならば、f の表を単色長方形に分割するには、少なくとも 2^k + 1 個以上の長方形が必要である。すなわち、D(f) \geq k + 1 である。

単色長方形の数を1個余計に数えているのは、別の値をとる入力の分です。

これにてすべての準備が整いました。いよいよ本題の証明に入ります。

EQ の通信複雑さ

それでは本題をさらっと証明してしまいましょう。

定理6: D(\mathrm{EQ}) = n + 1

入力の集合は \mathcal{X} = \mathcal{Y} = \{0,1\}^n なので、関数の表は 2^n \times 2^n の行列です。関数 \mathrm{EQ} の定義から、これが 2^n 次の単位行列であることも判ります。

Fooling set として対角成分すべてを取ります。すなわち、S = \{ (a,a) : a \in \{0,1\}^n \} です。これが fooling set であることは明らかでしょう。個数は 2^n 個ありますね。

よって、補題5より D(\mathrm{EQ}) \geq n + 1 を得ます。

上界と合わせて等号を得られるので、証明できました。

あっという間でしたね。上で積み重ねてきた道具がいかに強力であるかを思い知ったでしょうか?それらも所詮は自明なことの積み重ねに過ぎませんでしたが、このように非自明な結果を導くことができたというわけです。

前回と今回にわたって我々が証明したことをおさらいすると、アリスとボブが自分たちのデータが完全に一致しているかどうかをチェックするとき、乱数を使わず誤り率を一切妥協しないと、どうやっても対象のデータをそのまま送信するのと同じだけの通信量を要してしまうということでした。これは、初回に乱数を使って示したこととは裏の関係にあります。「アリスとボブは妥協する」から「アリスとボブは妥協しなければならない」というより強いことが言えたわけです。

妥協の効果、乱数の威力をお分かり頂けたでしょうか。これにて3回の話を締めさせて頂きます。それではまた次のトピックで。