通讯复杂性简单介绍

英文是 communication complexity ，不知道该翻译成通信复杂性，还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域，在过去 30 年衍生了很多东西。它是我的研究的主要内容，这里简略介绍一下。

1. Communication Protocol 通讯协议

我们说一个通讯问题，是有两台机器 Alice 和 Bob ，它们需要计算某个函数 f(x,y)f(x,y) 。但是 Alice 只知道输入xx ， Bob 只知道yy 。它们之间离得很远，需要通过光缆互相传递信息，把f(x,y)f(x,y) 计算出来。它们之间传递信息的过程称为通讯，一个有效的通讯过程称为一个协议。

举一个例子，比如两个数据中心，它们想知道它们的数据是否已经同步(指数据完全一样)，如果不一样的话就需要重新同步。它们之间该怎么通讯来确定这一点呢？这个问题就是通讯问题 EQ。在这个问题里， Alice 和 Bob 分别拥有一个字符串xx 和yy ，它们想计算x==yx==y 。

对于所有通讯问题， Alice 可以通过发送它的所有输入xx 到 Bob ，然后 Bob 拥有全部输入，从而计算f(x,y)f(x,y) 。注意在通讯问题里面，我们只考虑通讯消耗，而不考虑本地的计算时间和空间消耗。我们能设计更好的通讯协议吗？

对于一个通讯问题，如果要求对于任何输入，输出结果完全精确，这种符合条件的协议称为确定型通讯协议。但在实际应用中，我们可以容忍一个足够小的出错概率。在某些时候这是有很大好处的。比如上面那个 EQ 通讯问题，在要求结果完全精确的情况下， Alice 发送自己的xx 已经是一个最优方案了。但在实际应用中，我们有一个更简单的方法，那就是发送hash 函数（比如 MD5 码），然后双方检验 MD5 码即可。当然某种意义上这个协议不够严格，更严格的应该是 Alice 随机选择一个合适长度的质数pp ，然后发送(p,xmodp)(p,xmodp) 。

2. Communication Complexity 通讯复杂性

复杂性的意思就是说一个问题不能以多快的速度解决。比如 EQ 的任何确定型通讯协议无法比发送所有输入做得更好，这说明 EQ 的复杂度为O(n)O(n) 。类似于计算理论，人们发现证明一个复杂性比设计一个算法和协议更困难。

3. 量子通讯复杂性

量子通讯和上面的经典通讯基本上是一样的，除了 Alice 和 Bob 是两台量子计算机，可以操纵量子比特，以及它们之间共享量子通道可以发送量子比特。我们希望能够尽可能少的发送量子比特就能解决问题。

就像在计算理论里，人们非常关系量子系统的引入能否大幅度提高计算的速度，人们也关心量子系统对于通讯的帮助。目前，人们发现对于 partial 函数(对于某些输入对(x,y)(x,y) ，f(x,y)f(x,y) 可以没有定义的ff 称为 partial 函数)，量子系统可以指数级的缩减发送的比特数，但对于完全函数(对∀(x,y)∀(x,y) ，f(x,y)f(x,y) 都有定义)，人们猜测量子系统是没有帮助的。

4. 通讯复杂性理论和信息论

通讯复杂性理论和信息论是两个不同的领域。通讯复杂性通常研究如何发送尽可能少的比特得到计算结果，而信息论是研究通讯的过程(?)，比如如何纠错，如何利用量子纠缠等。现在的量子信息论发展非常火热，但和量子通讯复杂性是两个完全不同的概念。

5. GT 一个更复杂的例子

现在 Alice 和 Bob 分别拥有两个字符串xx 和yy ，它们该如何确定谁的字符串更大(按字典序)呢？同样这里很低的错误概率是可以忍受的。

思路：每次 Alice 和 Bob 先检查前一半输入是否相等（调用 EQ 的通讯协议），如果是，抛弃之；否则后一半可以抛弃；重复这个步骤即可。

Q. E. D.