计算理论的一个分支，与计算复杂性不同的是，通信复杂性不考虑计算的效率，而仅仅考虑通信的比特数。通信复杂性的概念有A.C.Yao提出，经过几十年的发展已经成为一门比较成熟的学科。通信复杂性又分为确定性协议和非确定性协议的通信复杂性，而非确定性协议的通信复杂性又分为公用随机序列与私用随机序列的通信复杂性。其中，对随用随机序列的通信复杂性的下界的研究能够证明设计协议是否最优。