第五百二十五章 姚期智的网络通讯复杂性理论
        我们说一个通讯问题，是有两台机器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随机选择一个合适长度的质数，然后发送。

        复杂性的意思就是说一个问题能以多快的速度解决。

        比如EQ的任何确定型通讯协议无法比发送所有输入做得更好，这说明EQ的复杂度为O(n)。

        类似于计算理论，人们发现证明一个复杂性比设计一个算法和协议更困难。

        【本章阅读完毕，更多请搜索墨缘文学网;http://wap.mywenxue.org 阅读更多精彩小说】

更多完整内容阅读登陆

《墨缘文学网，https://wap.mywenxue.org》