【理论学习】通信复杂度中的下界技术

发表于 2024-11-11 分类于理论学习

文献：Computational Complexity: a Modern Approach

定义

设是一个函数，计算的-回合通信协议指的是个函数的序列。通信过程如下：

Alice收到输入，Bob收到输入，

Alice发送给Bob，

Bob收到后，发送给Alice，

Alice收到后，发送给Bob……

这样来回，直到发送最后一个消息。

如果最后一个消息是，我们就说这个协议是有效的。

协议的通信复杂度指，即在任意输入上，该协议交换的信息的长度。

（在该模型下其实信息长度也就是回合数，因为每回合只传输一比特。当然，也可扩展到每回合消息长度不定的情形。）

函数的通信复杂度为所有有效协议中最低的通讯复杂度，记为。

显然的是，对于任意函数，都有，即Alice把完整地发给Bob，Bob算完后把结果发出来。（这里没有严格采用来回一bit一bit的模型要求）

值得注意的是，在考虑通讯复杂度时，我们不在乎任何一方在做自己那边的计算时要消耗多少资源，我们仅仅在意交换的信息量。我们事实上假设双方的计算能力都是无穷的，甚至能计算停机问题这类不可计算问题（听起来有些矛盾）。

第一个下界技术叫做诈集方法（fooling sets）。它是说，我们要尽量找出一族输入，它们使得通讯复杂度至少要超过某个规模，这族输入就叫做“诈集”。

例子：

考虑函数。

我们断言，该函数的通信复杂度。

考虑全体形如的输入，记为。由于的长度为，因此这样的输入有种。注意，对于任意中的输入，都有。

假设协议的通信复杂度至多为，则整个通信信息串只有种。则显然，中至少有个不同的输入，通信信息串相同。（参考资料里“只有种通信协议”的表述我觉得不对）

注意到，若协议对的通信是相同的，则该协议对这四个输入的通信也必然都是相同的！（站在双方的视角进行归纳很容易证明）

而由于，矛盾。

因此。

一般的，对于函数，如果存在大小为的输入集合和值，使得对任意成立；且对于任意中不同的有序对，要么，要么，

则该集合称为的诈集，

且

值得一提的是，这个诈集方法和我们之前提到的Myhill–Nerode Theorem是相似的。有多少个两两不等价的类，状态机就至少需要多少个状态。

这是通信复杂度下界技术中最根本的方法，这里根本的意思是。其他技术能得出的下界，铺彻方法必然也能得出。个人认为，它的根本性来源于它的组合枚举性。值得一提的是，这是一个2018年才出现的技术。

的矩阵是一个的矩阵，其中位置的值为，

也即。

矩阵的一个组合矩形（也叫矩形）是抽取属于中的所有元素组成的一个子矩阵，其中。（在直观图形上并不一定是个连续矩形，但可以通过swap行列变成一个直观上的矩形）

如果一个组合矩形的所有元素都是同一个值，那我们就称这个矩形是一个单色矩形，称是单色的。

的一个单色铺彻指的是将划分为一些不相交的单色矩形。

在的所有单色铺彻中，最少的单色矩形个数记为。

那么有：

另外：

如果存在大小为的诈集，则

待续…