两方通信模型

形式陈述 ​

模型数据 ​

本页先取有限非空输入集 $X,Y$ 与有限非空输出集 $Z$。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$。讨论对所有输入都可解的关系时，要求每个 $(x,y)$ 至少允许一个输出。输入空间写成笛卡尔积公理库笛卡尔积Cartesian product · Direct product of sets由各坐标分别取值形成的有序元组集合；二元情形记作 A×B。并不表示 $x$ 与 $y$ 随机独立；它只规定谁看到哪一部分信息。

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

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

有限承诺域 ​

也可声明非空承诺域 $D\subseteq X\times Y$，只要求在 $D$ 上计算给定函数或找到合法关系输出。协议的消息规则仍定义在整个乘积空间上，终止并输出某个标签；本页按整个空间计通信硬上限，但承诺外的答案不计正确性。用 $\ast$ 标记未定义输入时，$D$ 正是非 $\ast$ 的格。固定 transcript 在整个空间切出矩形，在合法输入中则只留下该矩形与 $D$ 的交；承诺本身不必是矩形。

一次协议怎样执行 ​

固定一个确定性协议 $\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 是双方逐步缩小这些可能世界的公开证据，但不是任何一方的完整知识。收到同一条消息的两个 Bob，可能因各自的 $y$ 不同而得出不同答案；只有额外要求公开叶标签时，答案才完全由 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 输出，Alice 发送 $a(x)$ 后就能停止；Bob 用自己的 $b(y)$ 算出结果，最坏只需一 bit。原协议中的第二条消息，是为了让 Alice 也知道结果。因而比较“同一个 AND 问题”的一 bit 与两 bit 上界时，先检查答案要交给谁，不能把差异归咎于算法优劣。

模型边界 ​

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

推论与应用

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

Streaming、sketch、分布式数据结构和网络计算常通过输入切分归约到两方通信。例如一个单遍流算法只保留 $s$ bit 状态，Alice 可先处理由 $x$ 生成的前半段，把状态发给 Bob；Bob 接着处理由 $y$ 生成的后半段并输出。这给出 $s$ bit 的单向模拟，前提是生成后的流答案恰好编码目标函数，且随机性可按原模型共享或延续。多遍扫描还需在下一遍开始前把状态送回，不能继续按一次消息收费。线性通信下界只有完成这样的模拟后，才会成为空间下界。

参考资料

• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapters 1–2.
• Tim Roughgarden, Communication Complexity (for Algorithm Designers), 2015，作者讲义，第 1.8 节的流算法模拟与第 4.2 节的两方协议。
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 1–2.