单向通信复杂度

单向协议的形式 ​

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

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

发送后不再接收 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^{\to }(f)$ 是所有正确编码器—解码器对中最小的 $c$。变长消息也可以研究，但必须采用可自定界编码并对最坏消息长度计费，不能把终止时间当作额外免费信息。

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

消息是一份面向所有 Bob 输入的摘要 ​

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

$$\mathrm{\forall }y\in Y,f(x,y)=f(x^{\prime },y).$$

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

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

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

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

这也解释了方向为什么重要。消息不是对 $x$ 的通用压缩，而是针对 Bob 将来怎样使用它的充分摘要。交换双方后，待区分的对象从矩阵的行变为列，复杂度可能发生显著变化。

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

令 Alice 持有 $x=x_1\cdots x_n\in \{0,1{\}}^n$，Bob 持有索引 $i\in \{1,\dots ,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^{\prime }$ 产生相同消息，却在某个位置 $i$ 不同，那么 Bob 取该 $i$ 时面对相同消息而需要输出两个值。确定性下界由此成为编码碰撞的不可避免性，而不是“输出看起来很难”的直觉判断。

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

考虑一个使用 $S$ bit 状态的一趟数据流算法公理库数据流算法模型Data-stream model · Streaming algorithm输入顺序到达且不能保存全文，以扫描趟数、工作空间、处理时间和输出保证评价算法。。把流切成前缀 ${\sigma }_A$ 与后缀 ${\sigma }_B$：Alice 在前缀上运行算法，将当前状态 $s({\sigma }_A)$ 发给 Bob；Bob 从该状态继续处理后缀并输出。若随机种子也属于协议双方的既知资源，这就得到一条至多 $S$ bit 的单向消息。

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

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

边界与比较 ​

若一般两方模型公理库两方通信模型Two-party communication model · Two-party communication complexity model两位参与者各自持有私有输入，只以交换消息协同计算函数或关系，并把通信位数作为核心资源。也只要求 Bob 输出，每个 Alice-to-Bob 单向协议都是其特例，所以交互复杂度不大于同口径的单向复杂度。若一般模型要求输出成为公开叶标签，则 Bob 还需回传输出编码，至多多出 $\lceil {\log }_2|Z|\rceil$ bit。反过来仍不成立：单向下界只排除没有反馈的消息结构，不能自动排除双方交替询问的协议。

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

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

参考资料

• 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.