两方通信模型

模型数据 ​

设 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 setsA×B 是所有第一分量来自 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 )$。

可追踪的两轮例子 ​

令 $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)$ 输出即可。

模型必须固定的口径 ​

确定性、私有随机币、公共随机币会产生不同协议族；零误差、单侧误差与双侧误差也有不同量词。以计算函数为例，最坏输入双侧错误至多 $\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$ 取期望，还是每次随机选择都受硬上限约束。只说“高概率正确、通信很少”不足以形成可比较的结论。

交互方向同样属于模型。Alice 先发一条消息的单向协议，允许 Bob 先提问再由 Alice 回答的两轮协议，以及双方任意交替的协议，能力可以不同。单向通信复杂度公理库单向通信复杂度One-way communication complexity限制 Alice 只向 Bob 发送一次消息，由 Bob 结合自身输入输出，并按消息 bit 数衡量代价。专门固定第一种限制；一般两方模型不会自动继承其下界。

关系问题还需声明合法输出集合和失败事件。若任务要求找出一个共同元素，存在多个共同元素时任取其一可能合法；若要求完整列出全部共同元素，输出长度本身已经造成通信。把这两个任务都写成“集合相交”会掩盖根本不同的输出语义。

最后，输出只有一个 bit 并不意味着通信只需一个 bit。输出压缩的是最终答案，不是双方在不知道对方输入时必须排除的可能世界。两方通信复杂度研究的正是这种知识差距，而不是输出文件的大小。

模型边界 ​

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

参考资料

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