一个比较大文件是否相等的最差也最好的确定性算法

相隔万里的两个人Alice和Bob每人拥有一个比特的字符串（文件）, 。二人的目标是，判断他们的两个文件是不是相等的，即对所有，是否 。

一个朴素的解法是Alice把他的整个文件发送给Bob，Bob检验对所有，是否 。然后将相等/不想等结果的这1比特发送回Alice。

显然当文件大小很大时，该解法要发送整个文件比特，通信复杂度过大。而且应该想不出比这更差（通信复杂度更高）的算法了，事实上我们有。

下面要说明的是，通信复杂度方面，没有任何的「确定性」算法比该最差的朴素算法更好。该结果可以帮助大家更好的理解「随机性」在算法设计中的巨大作用（且希望能启发读者去证明关于的新结果。）

通信复杂性理论是图灵奖得主姚期智先生的重要贡献之一。通信复杂度模型是对一个系统中的「通信复杂度」这一关键度量的建模，其理论结果对于后续的安全多方计算协议的通信开销和zkSNARKs的「简洁性」都具有重要的指导意义。下面先简述姚氏通信复杂度模型中的几个定义。

1姚氏通信复杂度模型

定义域 值域上的一个协议 ，是一个二叉树，每一个内部节点的标识为函数 或，每一个叶子结点的标识为元素。协议 在输入 上的值为从根开始在树上游走，到达叶子结点时该叶子结点的标识。对每个标识为 的内部节点，如果 向左游走，如果向右游走；对每个标识为 内部节点，如果 向左游走，如果向右游走。

协议 在输入上的开销为输入上路径的长度，协议的开销是树高。对函数，其确定性通信复杂度是对计算的所有所有协议， 最小的开销。

一个 上的Rectangle是一个子集，且对某个 和 使得 （是笛卡尔积）。

等价定义，是一个rectangle 当且仅当

记 是最终达到节点的输入输入 集合，一个协议的叶子节点集合为 ，则是对的一个划分。

一个集合是-monochromatic的如果的值在上不变。

可以证明是一个rectangle，且显然是-monochromatic的，则对一个函数的任何协议都可导出一个将 划分为-monochromatic rectangles的一个划分。rectangles的数量是的叶子节点数量。叶子节点数为，则二叉树深度即确定性通信复杂度：

集合 被称为的fooling set，如果存在值 使得：

• 对于任意.
• 对于任意两个中不同的对 ， ，要么，要么

假设一个monochromatic rectangle 包含两个不同的属于的对 和 ，则其一定包含 和 。然而由于是fooling set，的值在 和 上都是，但是至少在 或 之一上和不同，于是 不是monochromatic的，矛盾。所以每个monochromatic rectangle都至多包含一个中的元素。因此至少需要个rectangles来覆盖，因此再由上述结论可得，如果具有大小为的fooling set ，那么.

2问题定义

相等函数，当 时定义为1，否则定义为0。求

3下界证明

对于任意，；对于任意

于是可给出一个大小为的 fooling set ：

由上述可得 .

上述只考虑了1-rectangles，如果也将0-rectangles加入计数，集合大小翻倍，则得到。

再结合上界，可得，意即下界紧致。

于是该朴素算法为最差也最好的确定性算法。