通信複雑性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/08 03:46 UTC 版)
通信複雑性(つうしんふくざつせい、Communication Complexity、CC)は、1979年にアンドリュー・チーチー・ヤオによって導入された用語である。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。
- 1 通信複雑性とは
- 2 通信複雑性の概要
- 3 量子通信複雑性
通信複雑性と同じ種類の言葉
- 通信複雑性のページへのリンク