确定性通信复杂度 | Codeboy's Blog

形式陈述

复杂度的量词

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

C(\Pi)=\max_{(x,y)\in X\times Y}c_\Pi(x,y).

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

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

这里先对每个协议找最坏输入，再在所有全局正确协议中取最小值。若倒换为逐输入选协议，就允许不同输入采用不同的有利执行路径，测量的已是另一件事。更严重的错误是连“全局正确”也改成“只在当前输入正确”：此时设计者可直接硬编码该输入的答案，通信问题才会退化为零成本。上标 $\mathrm{cc}$ 用来区别查询复杂度中同样常写成 $D(f)$ 的量。

每条协议先对输入通信量取行最大值，再在协议之间选择最小的最坏代价 — 确定性通信复杂度的 min-max 量词

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

对有限承诺域 $D\subseteq X\times Y$ 上的函数，最优化只要求协议在 $D$ 内正确；协议仍在全空间终止，成本按全空间最坏长度计。承诺外标签任意，不应先选定一个 total completion 再把它的全部正确性要求加给原任务。

搜索关系的同一计费规则

对有限非空集合 $X,Y,Z$ 和总搜索关系 $R\subseteq X\times Y\times Z$ ，要求每个输入对 $(x,y)$ 至少有一个合法输出 $z$ 。仍使用上述确定性公开叶标签协议，定义

D^{\mathrm{cc}}(R) =\min_{\Pi:\ (x,y,z_\Pi(x,y))\in R\ \forall(x,y)} \max_{(x,y)\in X\times Y}c_\Pi(x,y).

不同输入对可以允许多个答案；一片叶子只需带有一个对所有到达该叶的输入都合法的固定标签。因此，共享 transcript 要求的是存在共同合法输出，而不是关系为每个输入指定同一个唯一值。把 $R$ 取为函数 $f$ 的图像，就恢复前面的定义。公开输出约定保持不变，本地寻找合法答案的计算仍不计费。

上界需要一条完整协议

证明 $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 复杂度。

直觉

双方本地计算免费，真正稀缺的是把各自私有输入中与输出有关的区别传给对方。确定性协议对每个输入只有一条 transcript；同一 transcript 中的输入必须不可区分且输出相同，所以复杂度来自需要多少不同对话区域，而不是输出 alphabet 本身有多大。

例子与边界

一个恰好一 bit 的函数

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

g(x,y)=x_1.

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

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

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

一 bit 输出仍可能要求线性通信

对 $n$ 位串的 Equality，考虑全部 $2^n$ 个相等输入 $(x,x)$ 。若两个不同的 $(x,x)$ 、 $(x',x')$ 到达同一个公开输出为 $1$ 的叶，叶对应的组合矩形还必须包含 $(x,x')$ ，但它的正确输出是 $0$ 。因此每个这样的叶最多容纳一个相等输入，至少需要 $2^n$ 个叶。深度 $c$ 的二叉树至多有 $2^c$ 个叶，故 $c\ge n$ 。

发送整个输入再返回答案给出 $n+1$ 的上界，所以本页已经得到 $n\le D^{\mathrm{cc}}(\mathrm{EQ}_n)\le n+1$ 。这足以说明线性通信障碍；不必把仅证出的下界误写成某个输出约定下的精确值。

推论与应用

transcript 与不可区分性

固定一个 transcript 后，所有产生它的输入对到达同一公开叶。对函数，这些输入必须具有同一函数值；对搜索关系，叶标签必须是它们共同允许的答案。协议树把这一事实画成根到叶的路径，通信矩阵则把同一批输入视为一个组合矩形。确定性下界通常证明：少于某个深度的树没有足够多合法叶，或某个叶不得不混入两个不同输出。

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

口径与失败边界

如果一轮可以发送任意大“符号”，却只把符号个数记作通信量，复杂度会被人为压成常数。标准口径按 bit 计费；要用固定长度编码区分字母表 $\Sigma$ 的全部符号，最坏需要 $\lceil\log_2|\Sigma|\rceil$ bit。变长编码可以让某些符号更短，却必须交代可解码性和最坏或平均长度。以 field element、word 或 packet 报告代价时，也必须同时声明其 bit 宽。

在同样的函数或总搜索关系任务、公开输出与最坏成本口径下，确定性零误差协议是随机通信协议中不使用随机币且错误为零的特例。允许非零错误后，最优通信量可以降低，不能把某条固定随机轨迹的确定性树当作全局正确协议。固定随机币确实得到一棵确定性树，但它可能只在部分输入上正确；错误概率来自许多这种树的分布，而不是其中任意一棵都正确。

轮数限制同样可能改变最优值。本页的 $D^{\mathrm{cc}}(f)$ 默认允许有限次交互并统计总 bit 数；若只许 Alice 发一次消息，应使用单向模型的记号。单向协议给出一般交互协议的上界，但单向下界不能直接证明一般 $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.

形式陈述 ​

复杂度的量词 ​

搜索关系的同一计费规则 ​

上界需要一条完整协议 ​

一个恰好一 bit 的函数 ​

一 bit 输出仍可能要求线性通信 ​

transcript 与不可区分性 ​

口径与失败边界 ​

反向链接