第五百九十一章 姚期智的网络通讯复杂性理论（2/2）

我们能设计更好的通讯协议吗？

对于一个通讯问题，如果要求对于任何输入，输出结果完全精确，这种符合条件的协议称为确定型通讯协议。

但在实际应用中，我们可以容忍一个足够小的出错概率。

在某些时候这是有很大好处的。比如上面那个eq通讯问题，在要求结果完全精确的情况下，alice发送自己的x已经是一个最优方案了。

但在实际应用中，我们有一个更简单的方法，那就是发送hash函数（比如md5码），然后双方检验md5码即可。

当然某种意义上这个协议不够严格，更严格的应该是alice随机选择一个合适长度的质数，然后发送。

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

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

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