确定性通信复杂度

复杂度的量词 ​

给定有限输入集上的函数 $f:X\times Y\to Z$，确定性协议 $\mathrm{\Pi }$ 不使用随机币。对每个输入对 $(x,y)$，双方的消息规则产生唯一 transcript，并在终止时输出 $f(x,y)$。记该次执行发送的总 bit 数为 $c_{\mathrm{\Pi }}(x,y)$，协议的最坏通信代价为

$$C(\mathrm{\Pi })=\underset{(x,y)\in X\times Y}{max}{c}_{\mathrm{\Pi }}(x,y).$$

$f$ 的确定性通信复杂度定义为

$$D^{\mathrm{cc}}(f)=\underset{\mathrm{\Pi }\text{ 正确计算 }f}{min}C(\mathrm{\Pi }).$$

这里先对每个协议找最坏输入，再在所有正确协议中取最小值。顺序不能倒换：若允许针对每个 $(x,y)$ 单独选择协议，设计者就等于预先知道双方输入，通信问题会消失。上标 $\mathrm{cc}$ 用来区别查询复杂度公理库确定性与随机查询复杂度Deterministic query complexity · Randomized query complexity在坐标访问模型中分别定义确定性、零误差随机和有界误差随机查询复杂度，并固定最坏与期望口径。中同样常写成 $D(f)$ 的量。

“正确”表示零误差：每个合法输入都必须到达公开标有正确输出的叶。本页因此采用 transcript 决定输出、双方都能读出答案的 convention；只要求 Bob 本地输出的版本可能少最后一条输出消息。协议可有不同长度的路径，但 $C(\mathrm{\Pi })$ 只看最深路径。若研究输入分布下的平均通信，应把期望分布与概率空间另行写出。

上界需要一条完整协议 ​

证明 $D^{\mathrm{cc}}(f)\le c$，需要描述一条对所有合法输入都正确、且每条执行路径至多发送 $c$ bit 的协议。只列一段压缩后的“关键信息”还不够：接收方必须能由自己的输入和收到的消息唯一确定输出，消息边界与终止条件也不能依赖未公开的信息。

最直接的通用协议是 Alice 把整个 $x$ 发送给 Bob。若 $x$ 有固定 $n$ bit 编码，Bob 本地计算 $f(x,y)$，再发送输出的固定编码。对 Boolean function，这给出

$$D^{\mathrm{cc}}(f)\le n+1.$$

若只指定 Bob 输出，可以省去最后一 bit；对一般 $Z$，应加上输出编码长度。这个上界粗糙却重要：它明确了通信按输入编码长度而不是抽象集合基数直接计费。若 $X$ 没有固定编码，写“发送 $x$”并没有给出 bit 复杂度。

一个恰好一 bit 的函数 ​

设 $x,y\in \{0,1{\}}^n$，并定义

$$g(x,y)=x_1.$$

Alice 发送 $x_1$，该 bit 同时成为公开叶标签，故有 $D^{\mathrm{cc}}(g)\le 1$。若不发送任何 bit，公开 transcript 对所有输入相同；取第一位分别为 $0$ 与 $1$ 的两个 Alice 输入，正确输出相反，因此零通信协议不可能正确。于是

$$D^{\mathrm{cc}}(g)=1.$$

这个例子同时否定两种草率估计。双方输入各有 $n$ bit，并不迫使通信达到 $2n$；函数只依赖 Alice 的一个坐标。另一方面，输出确实只有一 bit，但“一 bit 输出”本身也没有给出上界；真正的一 bit 协议来自发送的 bit 本身已经是答案。

transcript 与不可区分性 ​

固定一个 transcript 后，所有产生它的输入对对协议而言不可区分，因此必须要求这些输入拥有同一输出。协议树公理库协议树与通信 transcriptProtocol tree · Communication transcript用逐 bit 的有根树表示完整通信策略，并把一次执行产生的根叶路径区分为 transcript。把这一事实画成根到叶的路径，通信矩阵公理库通信矩阵与组合矩形Communication matrix · Combinatorial rectangle将两方函数排成输入行列矩阵，并以行集和列集的笛卡尔积刻画协议能够共同隔离的区域。则把同一批输入视为一个组合矩形。确定性下界通常证明：少于某个深度的树没有足够多合法叶，或某个叶不得不混入两个不同输出。

这类论证不是单纯比较输出种类数。布尔函数只有两个输出，仍可能需要许多 transcript，因为每个输出的输入区域可能被双方私有信息切成大量不能合并的部分。输出标签相同的多个叶也不一定能合成一个更短协议；合并后双方或许无法在不通信的情况下确认自己落在哪个输入区域。

口径与失败边界 ​

如果一轮可以发送任意大“符号”，却只把符号个数记作通信量，复杂度会被人为压成常数。标准口径按 bit 计费；使用字母表 $\mathrm{\Sigma }$ 时，一条符号至少对应 $\lceil {\log }_2|\mathrm{\Sigma }|\rceil$ bit 的区分能力。以 field element、word 或 packet 报告代价时，也必须同时声明其 bit 宽。

若协议允许随机币和非零错误，得到的是随机通信复杂度公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。，不能把某条固定随机轨迹的确定性树当作全局正确协议。固定随机币确实得到一棵确定性树，但它可能只在部分输入上正确；错误概率来自许多这种树的分布，而不是其中任意一棵都正确。

轮数限制同样可能改变最优值。本页的 $D^{\mathrm{cc}}(f)$ 默认允许有限次交互并统计总 bit 数；若只许 Alice 发一次消息，应使用单向模型公理库单向通信复杂度One-way communication complexity限制 Alice 只向 Bob 发送一次消息，由 Bob 结合自身输入输出，并按消息 bit 数衡量代价。的记号。单向协议给出一般交互协议的上界，但单向下界不能直接证明一般 $D^{\mathrm{cc}}(f)$ 的下界。

最后，免费本地计算使确定性通信下界很稳健，却让上界未必可执行。消息函数若需要指数时间，仍是合法的通信协议；将其称为高效分布式算法还需额外证明本地时间与存储界。

参考资料

• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapter 1.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 1–3.
• Alexander A. Razborov, “Communication Complexity,” in An Invitation to Mathematics, Springer, 2011, pp. 97–117.