通信複雜性

通信複雜性，計算理論的一個分支，與計算複雜性不同的是，通信複雜性不考慮計算的效率，而僅僅考慮通信的比特數。

基本介紹

• 中文名：通信複雜性
• 類型：計算理論的一個分支
• 特點：通信複雜性不考慮計算的效率
• 提出者：A.C.Yao

通信複雜性的概念有A.C.Yao提出，經過幾十年的發展已經成為一門比較成熟的學科。通信複雜性又分為確定性協定和非確定性協定的通信複雜性，而非確定性協定的通信複雜性又分為公用隨機序列與私用隨機序列的通信複雜性。其中，對隨用隨機序列的通信複雜性的下界的研究能夠證明設計協定是否最優。