两方通信模型

形式陈述 ​

模型数据 ​

设 Alice 持有 $x\in X$，Bob 持有 $y\in Y$。目标可以是一个函数公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。

$$f:X\times Y\to Z,$$

也可以是关系 $R\subseteq X\times Y\times Z$：函数要求输出唯一的 $f(x,y)$，关系问题只要求输出某个满足 $(x,y,z)\in R$ 的 $z$。输入空间写成笛卡尔积公理库笛卡尔积Cartesian product · Direct product of sets由各坐标分别取值形成的有序元组集合；二元情形记作 A×B。并不表示 $x$ 与 $y$ 随机独立；它只规定谁看到哪一部分信息。

双方依次发送有限 bit 串。每条消息可以依赖发送者自己的输入、此前公开的全部消息，以及模型允许的随机币，却不能直接读取对方的私有输入。完整消息序列称为 transcript。协议终止时，指定的一方或双方从自身视图确定输出；若采用叶结点公开标记输出的约定，双方从同一 transcript 到达同一结果。

模型刻意把本地计算设为免费。Alice 可以对 $x$ 做任意复杂的预处理，Bob 也可以无限制计算 $y$ 与已收到的消息；代价只累计真正跨越边界的 bit。这个抽象隔离了“数据分散在两处”造成的信息瓶颈，但不承诺协议能在现实机器上高效实现。

一次协议怎样执行 ​

固定一个确定性协议 $\mathrm{\Pi }$。第 $i$ 条消息可写成

$$m_i={\varphi }_i(x,m_{<i})\text{或}{m}_i={\psi }_i(y,m_{<i}),$$

取决于这一轮由谁发言。对给定 $(x,y)$，这些规则唯一决定 transcript $\pi (x,y)$。本次执行的通信量是各消息长度之和

$$c_{\mathrm{\Pi }}(x,y)=\sum _i|m_i|.$$

最坏输入代价为 $\underset{(x,y)\in X\times Y}{max}{c}_{\mathrm{\Pi }}(x,y)$。逐 bit 协议可以展开成一棵二叉协议树：每个内部结点标明当前发言者，其发出的 bit 选择下一条边；每个叶结点标明输出。固定输入对从根走到唯一叶结点，路径标签就是 transcript，路径长度就是通信量。树的表示也说明，变长消息中的沉默、结束符和边界不能被暗中当作免费信道。轮数统计发言权在双方之间切换的阶段，与总 bit 数是两个不同参数。

输入规模也必须显式给出。常见情形是 $X=Y=\{0,1{\}}^n$，复杂度随 $n$ 形成一个函数族；若 Alice 与 Bob 的输入长度不同，就应分别保留 $n_A,n_B$。渐近记号公理库渐近记号Asymptotic notation · Big O notation忽略常数和低阶项，比较函数在输入趋于无穷时的增长速度。只能隐藏与这些参数无关的常数，不能把错误率、轮数或消息字长一并吞进 $O(\cdot )$。

模型必须固定的口径 ​

确定性、私有随机币、公共随机币会产生不同协议族；零误差、单侧误差与双侧误差也有不同量词。以计算函数为例，最坏输入双侧错误至多 $\epsilon$ 表示

$$\underset{(x,y)\in X\times Y}{sup}{\text{Pr}}_R[\mathrm{\Pi }(x,y;R)\ne f(x,y)]\le \epsilon ,$$

概率只对协议允许的随机币 $R$ 取得。随机协议还要说明通信量是对 $R$ 取期望，还是每次随机选择都受硬上限约束。只说“高概率正确、通信很少”不足以形成可比较的结论。

交互方向和输出规格也属于模型。单向协议公理库单向通信复杂度One-way communication complexity限制 Alice 只向 Bob 发送一次消息，由 Bob 结合自身输入输出，并按消息 bit 数衡量代价。、固定轮数与任意交互的能力可以不同；关系问题则需声明合法输出集合，以及只找一个见证还是列出全部见证。输出只有一个 bit 也不意味着通信只需一个 bit，因为协议仍须排除由对方私有输入造成的许多可能世界。

直觉

两方模型把计算拆成两座各自拥有私有视野的岛，本地推理免费，只有跨海消息计费。函数可能很容易在集中式机器上计算，却仍要求大量通信，因为任何一方都无法凭自己的输入排除对方那一侧的大量可能世界。

Transcript 是双方逐步缩小这些可能世界的公开证据。交互允许后一条消息针对前文提问或回应，因此同样的总 bit 可以形成不同知识路径；单向协议则必须一次准备好足以应对所有对方输入的摘要。

例子与边界

可追踪的两轮例子 ​

令 $a:X\to \{0,1\}$ 与 $b:Y\to \{0,1\}$ 是双方可在本地计算的谓词，目标为

$$f(x,y)=a(x)\wedge b(y).$$

Alice 先发送 $a(x)$。若该 bit 为 $0$，结果已经确定为 $0$，协议立即停止；若它为 $1$，Bob 再发送 $b(y)$，该 bit 就是最终输出。于是可能的 transcript 为 0、10、11，通信量分别为 $1,2,2$ bit，最坏代价为 $2$ bit。

这条轨迹说明本地输入可以很长，真正需要跨边界的却只是与目标有关的摘要。它也展示了交互为何可能产生不同长度的路径：第一条消息有时已经排除全部另一方输入，无须机械地跑满两轮。若协议规定只有 Bob 输出，那么在 transcript 0 上 Bob 已从 Alice 的消息知道答案；在另外两条路径上，他结合 $b(y)$ 输出即可。

模型边界 ​

通信模型隔离的是私有信息跨边界所需的 bit，而不是完整计算成本。它常被用来分析其他受限模型中的信息传递，但结论能否转移取决于具体归约是否保留输入划分、轮数、错误率和参数规模。反过来，一个低通信协议可能依赖指数时间枚举、无限精度算术或难以实现的消息函数，因此不会自动给出现实中的高效算法。通信下界说明存在信息障碍；运行时间、空间或 I/O 下界还需要额外论证。

推论与应用

协议树、通信矩阵与信息复杂度分别把同一模型投影为组合、代数和信息论对象。只要发送者的下一步确由本地 view 决定，就能用这些表示证明叶数、矩形纯度或输入泄露下界；不同工具共享模型接口，却测量不同障碍。

Streaming、sketch、分布式数据结构和网络计算常通过输入切分归约到两方通信。有效迁移必须逐项保留谁持有什么、状态怎样跨切口、pass 对应多少轮以及错误如何继承；线性通信下界只有完成这条模拟后，才会成为目标模型的空间或消息下界。

参考资料

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