通讯复杂性简单介绍

作者: , 共 1619 字

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