通信複雑性（つうしんふくざつせい、Communication Complexity、CC）は、1979年にアンドリュー・チーチー・ヤオによって導入された用語。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。もちろん、上記の例でアリスが n ビットの文字列全体をボブに送ってしまえば、ボブがその関数を計算でき、問題は解決する。しかし、ここで考えているのは、n ビットより少ない通信量で関数を計算する賢い手法の探索である。この抽象的な問題は様々な場面で応用できる。VLSIの回路設計では、消費電力を低減させるために、ある部分から別の部分に流れる信号の量を最小化したい場合がある。他にもデータ構造の研究やコンピュータネットワークの最適化にも関連する。応用に関しては、参考文献にある Kushilevitz と Nisan の著書に詳しい。formula_1: X formula_2 Y formula_3 Z としたとき、一般に formula_4 および formula_5 と仮定する。アリスは n ビットの文字列 formula_6 formula_7 X を持ち、ボブは n ビットの文字列 formula_8 formula_7 Y を持つ。一度に 1ビットずつ両者間で通信を行い（何らかの通信プロトコルが適用される）、アリスとボブは最終的にいずれかが formula_10 の値を計算できるようにしたい。取り決めとして、一方で答えが判明したらもう一方にあと 1ビットの通信をするだけで全通信が完了するものとする。この通信プロトコルの最悪の通信複雑性（formula_11 で表される）は次のように定義される。ここで関数 formula_12 を行列 formula_13（入力行列と呼ぶ）として考えるのが便利である。この行列の行は formula_6 formula_7 X に対応して並んでおり、列は formula_8 formula_7 Y に対応して並んでいる。入力行列の各要素は formula_18 である。初期状態でアリスもボブも行列 A 全体を知っている（つまり、両者は関数 formula_12 を知っている）。そうすると、関数の値の計算問題は対応する行列の要素を選び取る問題に変換される。この問題はアリスかボブのどちらかが formula_6 と formula_8 の両方を知った時点で答えがわかる。通信を開始するとき、答えとしてありうるのは行列の全要素なので formula_22 個存在する。その後、互いに 1ビットずつ通信すると、解ではあり得ない行や列が除外されていく。より形式的に表現すると、集合 R formula_23 X formula_2 Y があり、formula_25 formula_7 R かつ formula_27 formula_7 R のとき常に formula_29 formula_7 R ならば、R を長方形であるという。また、R を R = M formula_2 N （ただし、M formula_23 X かつ N formula_23 Y）であるような A の部分行列と見ることもできる。既に formula_34 ビットの情報をやり取りした状態を考えて見よう。ある formula_35 formula_7 formula_37 について、次のように行列が定義される。ここで、formula_41 formula_23 X formula_2 Y であり、formula_41 は長方形であると同時に A の部分行列である。ここでは、アリスとボブが同じ文字列を持っているかどうかを決定する問題を例として示す。つまり、formula_6 と formula_8 が等しいかどうかを判定しようということである。formula_6 と formula_8 が完全に等しいことを確認するには最悪ケースで formula_49 ビットの通信が常に必要になることは証明するのも簡単である。formula_6 と formula_8 がそれぞれ 3ビットという簡単な場合を考えて見よう。この場合の等価関数は下記のような行列で表される。行はありうべき formula_6 の値が並び、列には同様に formula_8 が並ぶ。見ての通り、この関数は formula_6 と formula_8 が等しい場所（対角線上）だけで 1 となる。1 ビット通信する毎に可能性が半分に分割されていく。formula_8 の最初のビットが 1 であると知っている場合、列の半分だけを考慮すればよい（formula_8 は 100, 101, 110, 111 のいずれかになる）。上述の定義では、通信は決定論的に行われると見なしている。両者が乱数発生器にアクセスする場合、formula_12 の値をなるべく少ない通信量で決定することはできるだろうか？ ヤオは彼の論文[1979]で乱択通信複雑性を定義することでこの問題の回答を与えた。関数 formula_12 のための乱択プロトコル formula_71 は、以下の両側誤りを持つ。乱択プロトコルは通常の入力以外に追加のランダム列を使用する決定論的プロトコルである。これには二種類のモデルがある。両者が事前に同じランダム列を共有している「公開ランダム列」と、一方が生成して他方に通信によって伝える必要のある「秘密ランダム列」である。後に説明する定理によれば、秘密ランダム列プロトコルで本来より "O(log n)" のビットを追加することで公開ランダム列プロトコルをシミュレート可能である。乱択複雑性とは単にこのようなプロトコルで交換するビット数として定義される。乱択プロトコルを片側誤りを持つような形式で定義することもでき、それに従って複雑性も同様に定義される。再び、"EQ" の例である。確実性が求められないなら、アリスとボブは等しいかどうかの判定を "O(log n)" 個のメッセージで行うことができる。次のようなプロトコルを考える。アリスとボブは同じランダム列 formula_72 にアクセスできるものとする。アリスは formula_73 を計算し、そのビット（"b" と呼ぶ）をボブに送信する。なお、formula_74 はGF(2)のドット積である。ボブは "b" と formula_75 を比較する。もし等しいならボブは "x" と "y" が等しいと言う事ができる。明らかに formula_76 なら formula_77 であり、従って formula_78 である。"x" と "y" が等しくない場合でも formula_77 である可能性はあり、その場合ボブは答えを間違う。これはどんなとき発生するだろうか？"x" と "y" が等しくない場合、それらの一部の位置で以下のように値が異なっているはずである:formula_6 と formula_8 が等しいなら、formula_82 であり、これによりドット積も等しくなる。従って、等しい項は無視して formula_6 と formula_8 が異なる部分だけを注目すればよい。さらに、ドット積が等しいかどうかに関わらず、ビット formula_85 とビット formula_86 を入れ替えることができる。つまり、formula_6 に 0 であるビットを集め、formula_8 に 1 であるビットを集めるよう入れ替えを行うこともできる。この場合、formula_89 および formula_90 となる。問題は、formula_91 であるようなランダム列 formula_92 が存在する可能性である。各 formula_93 は formula_94 である可能性と formula_95 である可能性が同じであるため、これを満足する文字列である可能性は単に formula_96 となる。以上より、formula_6 と formula_8 が等しくない場合、formula_99 となる。アルゴリズムを繰り返すことによって、その正確性を上げていくことが可能である。これは、乱択通信アルゴリズムの要求にも合っている。以上により、「アリスとボブが n ビットのランダム列を共有した場合」に互いに 1 ビットを送ることで formula_100 を計算できることを示した。次節では、"n" ビットのランダム列を共有するのと同程度に "O(log n)" ビットのやり取りで目的を達成する方法を示す。それにより、"EQ" が "O(log n)" 個のメッセージで計算できることを示す。両者がランダム列を共有できれば（共有ランダム列プロトコル）、乱択プロトコルを作成するのは簡単である。ランダム列を共有しない場合でも（秘密ランダム列プロトコル）、小さな通信コストで乱択プロトコルを構築することが可能である。n ビットの文字列を使った共有ランダム列乱択プロトコルは、追加の "O(log n)" ビットの通信を行う秘密ランダム列プロトコルでシミュレート可能である。直感的に、若干の誤りの増加を伴えば十分なランダム性を持った文字列の集合で乱択プロトコルを実行することができる。この集合は事前に両者で共有しておく。従って、アリスとボブはその集合のうち、どの文字列を使用するかに関して合意すればよい。このとき、文字列の集合は選択のための通信を効率的に行うためにも最小限でよい。形式的な証明は以下の通り。最大エラー率 0.1 の乱択プロトコル "P" を考える。formula_71 は長さ formula_49 の文字列が formula_103 個存在する集合であり、各文字列には formula_104 と番号が振られている。formula_71 を使った新たなプロトコル formula_106 は、無作為に formula_107 番の文字列を選択した上で、それを共有ランダム列として "P" を実行する。formula_107 を選択するのに必要な通信ビット数は "O(log 100n) = O(log n)" である。入力 formula_109 について、formula_110 と formula_106 が正しい値を得る確率をそれぞれ formula_112 と formula_113 と定義する。ある固定の formula_109 について、を使うと、次のような式が得られる:従って、formula_109 を任意とした場合、次のようになる:最後の等号は、formula_109 の組み合わせが formula_117 個あるからである。全ての formula_109 について以下が成り立つ formula_119 が存在する。formula_110 の最大エラー率は 0.1 であることから、formula_121 のエラー率は最大で 0.2 となる。量子通信複雑性は、分散計算に量子効果を適用して通信縮小を定量化しようという試みである。少なくとも3種類の通信複雑性の量子化手法が提案されている。詳しくは G. Brassard の調査結果を参照（参考文献）。第一のモデルは量子ビット通信モデルである。これは通信に従来的な手段ではなく、量子通信を用いるものであり、例えば光ファイバー上で光子をやり取りする。第二のモデルでは、通信は従来的なビットで行われるが、プロトコルの一部として無制限の量子もつれ状態を操作可能とするものである。両者のもつれ状態を測定することにより、分散計算での通信を減らすことができる。第三のモデルでは量子ビット通信に加えて、過去に共有されたもつれ状態へのアクセスができるとするものだが、3つのモデルの中では最も研究が進んでいない。0/1 入力行列 formula_122 について、formula_12 を決定するのにやり取りが必要な最小ビット数の最悪ケース formula_124 は、行列 formula_125 の階数の対数が下限となっている。対数階数予想（log rank conjecture）によれば、formula_125 の通信複雑性 formula_124 の上限は、formula_125 の階数の対数のべき乗である。D(f) の上限と下限が formula_129 の階数の対数の多項式であることから、D(f) は formula_129 の階数の対数に多項式的に関連していると考えられる。行列の階数は、そのサイズに対する多項式時間で計算可能であるため、通信複雑性の上限は多項式時間で計算可能と考えられる。ただし、行列のサイズは入力文字列の長さに対して指数的に増加する。乱択プロトコルでは、やり取りするビット数の最悪ケース R(f) は以下の式に多項式的に関連すると推測される:formula_131.このような対数階数予想は、行列の通信複雑性の問題を行列の線形独立な行（または列）の問題に帰着させるという点で有意義である。これは通信複雑性問題の本質を明らかにする。例えば、上述の EQ の場合でもそうだが、入力が等しいかどうかを判定するために、入力が行列のどの要素に対応するかを解明する問題に帰着させていたのであった。

出典:wikipedia