wikipedia

通信複雑性(つうしんふくざつせい、Communication Complexity、CC)は、1979年にアンドリュー・チーチー・ヤオによって導入された用語。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。
もちろん、上記の例でアリスが n ビットの文字列全体をボブに送ってしまえば、ボブがその関数を計算でき、問題は解決する。しかし、ここで考えているのは、n ビットより少ない通信量で関数を計算する賢い手法の探索である。
この抽象的な問題は様々な場面で応用できる。VLSIの回路設計では、消費電力を低減させるために、ある部分から別の部分に流れる信号の量を最小化したい場合がある。他にもデータ構造の研究やコンピュータネットワークの最適化にも関連する。応用に関しては、参考文献にある Kushilevitz と Nisan の著書に詳しい。

引き続き、communicationをテーマの中心にそえたアルゴリズム

具体例 その1
Alice (1、2、8、9)Bob(3、6、7)
それぞれが、整数の要素をもっている。相互の数字のやり取りを、ビット最小限にして
アリスとボブの数字の集合で最大の値をもつものを算出したい。(結論からいくと、ここではMax9)

アリスの集合と、ボブの集合の要素xとyを入力すると、あるoutputがでる
関数f(x,y)の計算結果を出したい。

アリスとボブの間で、情報(ビット)のやり取りをして、
具体例に応じた関数の計算ができる状態にする。

一番素朴なprotocol
アリスの集合をすべて、ボブに送信したら、ボブのほうで9の算出は可能。

もうすこし、送信する情報量を減らしたい。そして、おなじoutputが出せるようにしたい。

すこし、工夫したprotocol
アリスが、自分がもっている集合の要素のうち、最大のものだけを(この場合、9)送信する。
これでも、Bobのほうで、9の値を算出できる。

===
具体例その2
アリスとボブがそれぞれ、任意の整数の集合をもっていることは前の具体例と同じ。
今度は、2当事者が、通信する情報量を最小限にして、
二つの整数の集合を要素として、その整数の平均値がどちらかの当事者のほうで算出できるように
したい。(この場合、37を7で割る。)

ここでも、一番素朴なprotocolとして、アリスがボブにすべての情報を送信するという
選択肢はある。ただ、それでは、面白くないので、もう少し、情報量を減らして、おなじoutputが出せる
方法がないのかを考える。

アイディア1
アリスのほうで、自分の整数の集合の平均を出す。その平均の数字だけおくって、ボブのほうで
二人の平均を出させることはできるか?
結論 出来ない。なぜなら、これでは、アリスのほうでいくつの集合があったかボブは知ることができない。よって
平均の計算ができない。

アイディア 1の改良
アリスがボブに送信する情報に、「アリスがもっている整数の個数」を追加する。

これでも、送信する情報の量は減らせる。

具体例その3
アリスとボブがそれぞれinputとしてもっている整数を、小さいものから、大きいものの順番で並べたとき、
中央にくる値はいくらかを算出できるようにしたい。この場合、アリスとボブの間でやりとりする必要の
ある最小の情報はなにか?

(ここら辺から、すこし手が込んだものになる。)

具体例その5
アリスが行きたいお目当てのレストランの名前のリストは5つある。
ボブが行きたいお目当てのレストランの名前のリストは5つある。
二人はカップル。
アリスの頭の中でも、ボブの頭の中でも、両方にひらめいたレストランの名前を明らかにして
二人でそこに食事に行きたいというケース。

この「計算」をしたい場合、アリスかボブは、相手に対して、自分の頭に浮かんでいるすべてのレストランの
名前のリストを送信しないと、「双方に一致して意中にあるレストラン」が明らかになることはないそうです。

具体例 その4
アリスとボブの整数の集合要素を入力する。

要素の数の合計を数え上げる

もし合計の数値が偶数だったら0
もし、合計の数値が奇数だったら1
をそれぞれ算出する関数を考える。

この関数で、欲しい算出をさせるためにも
アリスかボブのほうで、自分がもっているすべての情報を相手に送信する必要がある。
それ以外の方法で、情報量を減らしてしまうと、正確に0,1を出すことはできないという
ことの数学的な証明。