单向通信复杂度 | Codeboy's Blog

形式陈述

单向协议的形式

在 Alice-to-Bob 的确定性单向协议中，Alice 根据私有输入 $x\in X$ 计算一条消息

m(x)\in\{0,1\}^*,

发送后不再接收 Bob 的任何信息。Bob 持有 $y\in Y$ ，用解码函数 $g$ 输出 $g(m(x),y)$ 。协议计算 $f:X\times Y\to Z$ ，当且仅当对所有 $(x,y)$ 都有

g(m(x),y)=f(x,y).

若消息固定为 $c$ bit，确定性单向复杂度 $D^{\rightarrow}(f)$ 是所有正确编码器—解码器对中最小的 $c$ 。变长消息也可以研究，但必须采用可自定界编码并对最坏消息长度计费，不能把终止时间当作额外免费信息。

随机单向协议允许编码器、解码器使用模型声明的随机币，并要求对每个固定 $(x,y)$ ，错误概率至多 $\varepsilon$ 。相应复杂度常写作 $R^{\rightarrow}_\varepsilon(f)$ 。公共币还是私有币、通信硬上限还是期望长度，都会改变精确定义；只写一个箭头不能替代这些口径。

函数行刻画

Alice 发送消息时看不到 $y$ ，所以同一 $m(x)$ 必须支持 Bob 随后面对每个可能的 $y$ 。两个 Alice 输入 $x,x'$ 可以安全地使用同一消息，当且仅当它们对 Bob 的全部输入都诱导相同输出：

\forall y\in Y,\qquad f(x,y)=f(x',y).

若存在某个 $y$ 让两者输出不同，Bob 在收到相同消息、持有该 $y$ 时便无法正确区分。因此确定性单向协议实质上把 $X$ 按函数行 $f(x,\cdot)$ 的相等关系编码；不同的行行为需要不同消息。

形式上可定义 $x\sim_f x'$ 当且仅当对所有 $y$ 都有 $f(x,y)=f(x',y)$ 。正确确定性消息必须把不同等价类分开；反过来，若 Alice 发送自己所属等价类的索引，Bob 就能由该类的共同函数行回答。

因此若共有 $N_f$ 个不同函数行，固定长度消息需要且只需 $\lceil\log_2N_f\rceil$ bit。这个等式描述的是无限本地计算下的最优编码；求等价类或存储完整函数行是否可行，仍不在单向通信度量内。

对关系问题，简单的“函数行相等”条件要改成解码可行性：同一消息类中的所有 $x$ ，对每个固定 $y$ 都必须存在一个 Bob 可输出、且对该类全部输入同时合法的答案。逐个输入各有某个合法答案，并不足以让 Bob 在不知道 $x$ 时选择同一个答案。

直觉

消息不是对 $x$ 的通用压缩，而是一份面向所有 Bob 输入的摘要。Alice 发信时不知道 $y$ ，同一编码必须让 Bob 在每个可能的后续情境中都能回答；只要两个 $x$ 在某一列产生不同输出，它们就不能安全碰撞。

这也解释了方向为何重要。Alice-to-Bob 区分函数矩阵的行，Bob-to-Alice 区分列；反馈则让发送者先得知对方真正关心的问题，再定制回答。看似只改变箭头或轮数，实质上改变了消息必须同时服务多少种未来。

例子与边界

单向模型允许 Alice 的消息直接到达 Bob，Bob 可结合自己的输入输出；同时消息传递模型要求 Alice 与 Bob 互不见对方消息，只把各自摘要发给 referee。缺少接收方反馈和直接通信会改变协议可表达的信息组合。

一个索引访问的执行图像

令 Alice 持有 $x=x_1\cdots x_n\in\{0,1\}^n$ ，Bob 持有索引 $i\in\{1,\ldots,n\}$ ，目标输出 $x_i$ 。Alice-to-Bob 的朴素协议把整个 $x$ 作为 $n$ -bit 消息；Bob 收到后读取第 $i$ 位。对输入 $x=10110$ 、 $i=4$ ，通信 transcript 就是 10110，Bob 输出 $1$ 。

若交换允许的方向，让 Bob 先发送 $i$ ，Alice 只需回传 $x_i$ 。索引编码使用 $\lceil\log_2 n\rceil$ bit，再加一 bit 回答；这已经不再是 Alice-to-Bob 的单向协议，而是另一方向加回复的两轮协议。这个对照没有证明朴素的 $n$ bit 一定最优，却准确展示了反馈能把“摘要全部可能问题”改成“回答一个已经公开的问题”。

任何声称 Alice 只发少量信息的方案，都应接受同样的视图检查：如果 $x$ 与 $x'$ 产生相同消息，却在某个位置 $i$ 不同，那么 Bob 取该 $i$ 时面对相同消息而需要输出两个值。确定性下界由此成为编码碰撞的不可避免性，而不是“输出看起来很难”的直觉判断。

边界与比较

若一般两方模型也只要求 Bob 输出，每个 Alice-to-Bob 单向协议都是其特例，所以交互复杂度不大于同口径的单向复杂度。若一般模型要求输出成为公开叶标签，则 Bob 还需回传输出编码，至多多出 $\lceil\log_2|Z|\rceil$ bit。反过来仍不成立：单向下界只排除没有反馈的消息结构，不能自动排除双方交替询问的协议。

消息长度按 bit 而非“对象个数”计。发送一个取值于 $M$ 种可能的符号，至少要有区分这 $M$ 种值的编码；把任意长向量叫作“一条消息”并不会使通信成为 $1$ 。同理，公共随机串若模型允许免费共享，它不是消息，但由随机串选出的哈希值仍须实际发送。

单向模型不限制 Alice 生成 $m(x)$ 的时间，也不限制 Bob 解码的时间。一个存在性编码可能要枚举全部输入才能求出；它给出通信上界，却未必给出高效 sketch 或数据结构。将通信结果迁回算法时，计算可实现性需要单独验证。

推论与应用

数据流状态为何形成单向消息

考虑一个使用 $S$ bit 状态的一趟数据流算法。把流切成前缀 $\sigma_A$ 与后缀 $\sigma_B$ ：Alice 在前缀上运行算法，将当前状态 $s(\sigma_A)$ 发给 Bob；Bob 从该状态继续处理后缀并输出。若随机种子也属于协议双方的既知资源，这就得到一条至多 $S$ bit 的单向消息。

这条转换保留的是“前缀处理完后唯一流向后缀的信息”。如果 streaming 算法有 $p$ 趟，状态会在切口来回传递，对应多轮协议，而不是仍然一条单向消息；如果算法把完整前缀写入未计费外部日志，消息也不再只有 $S$ bit。下界归约必须逐项保存这些资源条件。

线性摘要和分布式聚合也常有同一形状：Alice 发送 sketch，Bob 加入自己的更新后解码。能合并不表示消息无损；近似误差、失败概率与随机种子可见性必须随摘要一起带进通信协议。

不同函数行的精确计数给出确定性单向复杂度的完整刻画；在随机协议中，这种“完全分开”会放宽为用短随机消息近似区分行分布。Indexing、Equality 与 streaming sketch 的差异，正可从 Bob 需要恢复的是任意坐标、相等性判定还是近似统计量来理解。

参考资料

Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Sections 1.3 and 3.2.
Tim Roughgarden, Communication Complexity (for Algorithm Designers), 2015, Lectures 2–4.
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 2 and 4.

形式陈述 ​

单向协议的形式 ​

函数行刻画 ​

一个索引访问的执行图像 ​

边界与比较 ​