通信复杂性

（计算机科学技术）

通信复杂性（communication complexity），计算机科学技术名词，姚期智1979年提出的研究方向，假设有A， B双方分别持有输入( x，y )的 x 和 y ，两者都是 n 位的比特串，任何一方都不知道对方持有的输入，A， B将通过通信而联合计算函数值 f(x，y) ， f 的通信复杂性指为计算 f(x，y) ，A和B所需进行通信的位数。