通讯复杂性简单介绍

作者: , 共 1677 字 , 共阅读 0

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

1、Communication Protocol 通讯协议

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

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

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

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

2、Communication Complexity 通讯复杂性

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

3、量子通讯复杂性

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

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

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

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

5、GT 一个更复杂的例子

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

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

Q. E. D.

类似文章:
前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在这篇文章提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
相似度: 0.112
姚期智教授给清华大学新入学研究生开的一门课,课程内容:
相似度: 0.111
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个$ 2\times2$ 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是Andrew Yao的研究方向
从 hash 函数到王小云的 MD5 破解我们介绍了 hash 函数的一些基本概念和 MD5 碰撞的一个「应用」,最近在这个问题上又有了新的进展。
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分——hash 函数,以及王小云老师在这上面的工作。
比特币协议里使用了 ECDSA (椭圆曲线签名算法),我之前以为它和基于大数分解的 RSA 公钥密码体系差不多。这两天看了下维基百科,才发现它们之间的差异挺大。
IT » 比特币
最近 bitcoin 很火,我也是最先从云风那里了解到的,后来发现李笑来&霍炬对其都有涉及。不过他们对其具体技术原理的描述还是不够细致,所以我自己把bitcoin wiki又重新看了一遍。 看完之后,疑惑挺多,我对这个体系远没有前面三位这么乐观。诚然,它会成为"Geeks "手中的玩物甚至灰色交易的工具,但要说的达到「一出天下反」的程度,那还需要解决一些技术和金融方面的问题。
相似度: 0.071
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
前一篇:
$ n$ 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
姚期智教授给清华大学新入学研究生开的一门课,课程内容: