协议树与通信 transcript

形式陈述

树表示的是完整策略

取两方模型中最坏通信有有限上界、采用公开叶输出的确定性协议。把它的消息拆成逐 bit 发送，可得到一棵有根二叉树。每个内部结点标记当前发言者；若由 Alice 发言，离开该结点的边由她根据 $x$ 和此前路径选择，若由 Bob 发言则由 $y$ 与此前路径选择。标为 $0$ 、 $1$ 的两条边记录所发 bit，叶结点标记协议输出。

树本身收纳了协议对所有输入的响应规则。一次具体执行只走其中一条根叶路径，沿途的 bit 串

t=t_1t_2\cdots t_k

称为该执行的 transcript。它记录实际发生的公开对话，却不包含没有走到的分支，也不等于协议的完整程序。树的最大根叶深度就是逐 bit 口径下的最坏通信量，因此与确定性通信复杂度直接对应。

若原协议一次发送长消息，可以把这条消息展开成若干连续的同一发言者结点。反过来，把同一阶段的连续 bit 收拢为一个字符串不会改变总 bit 数，但会改变“轮”的计数。协议树首先编码信息量；若定理还限制轮数，就要在树上额外记录发言者切换。

树中还可能画出对任何合法输入都走不到的分支。它们不产生 transcript，也不覆盖输入；删去不可达子树不会损害正确性，通常还能缩短或保持最坏成本。叶数下界应统计可达叶，而不是把任意装饰结点也当作协议的信息能力。

若一条边标记的不是 bit 而是 $M$ 种消息之一，可以展开为二进制编码，但编码长度与消息概率、是否自定界有关。最坏通信下固定长编码需要 $\lceil\log_2M\rceil$ bit；按“一个符号”计费而不声明字母表，会让树深失去 bit 语义。

transcript 输入集为何是矩形

对任意树结点 $v$ ，记 $S_v$ 为走到该结点的输入对集合。根处 $S_{root}=X\times Y$ 。归纳假设 $S_v=A_v\times B_v$ 。若 $v$ 由 Alice 发言，她的下一 bit 只依赖 $x$ 与已经固定的路径，所以走向某个孩子只会把 $A_v$ 缩为子集 $A'_v$ ，而不会按 $y$ 进一步切分 $B_v$ ；孩子集合为 $A'_v\times B_v$ 。Bob 结点则对称地只缩小第二个因子。

对自然数深度使用数学归纳法，每个结点、特别是每个叶 transcript 的一致输入集，都是组合矩形。

若任务有非矩形承诺域 $D\subseteq X\times Y$ ，准确说法是：完整输入空间中到达该结点的集合为 $A_v\times B_v$ ，合法输入集合则是 $(A_v\times B_v)\cap D$ ，后者未必还是矩形。例如承诺 $x=y$ 时，即使零通信根结点的合法输入也只是一条对角线。不能因承诺域不是矩形，就误判局部通信规则失去矩形性质。

若协议正确计算函数 $f$ ，同一叶上的全部合法输入还必须具有相同 $f$ 值，因为叶只有一个输出标签。这正是通信矩阵与组合矩形之间的结构桥梁。

注意，证明只使用“发送者不知道对方私有输入”。如果某一步可以查询共享数据库、观察对方内存或让第三方按 $(x,y)$ 共同选择分支，孩子集合可能同时切分两个因子，矩形不变量就会失效。引用矩形下界之前，必须先确认目标算法确实能模拟为这种协议树。

直觉

协议树像一份覆盖所有可能对话的剧本，transcript 则是某次输入真正演出的那条台词序列。双方每一步只能依据自己的输入和已经公开的前缀选边，所以路径不是由知道 $(x,y)$ 的外部观察者事后挑出的；这个局部可执行性正是通信模型的限制来源。

矩形性质可以理解为“单方发言只切自己那一维”。Alice 的一 bit 会把可能的 $x$ 集合分开，却不能直接按 Bob 尚未透露的 $y$ 切割；Bob 的发言反之。一路交替切分后，每个 transcript 仍保留为两个集合的笛卡尔积。

三叶通信协议树与 transcript 0、10、11 对应的输入矩形 — 协议树与 transcript 矩形

例子与边界

一棵三叶协议树

设双方本地计算谓词 $a(x),b(y)\in\{0,1\}$ ，目标为 $a(x)\land b(y)$ 。Alice 在根发送 $a(x)$ 。若为 $0$ ，立即到达输出 $0$ 的叶；若为 $1$ ，Bob 再发送 $b(y)$ ，并分别到达输出 $0$ 或 $1$ 的叶。三条完整 transcript 是

0,\qquad 10,\qquad 11.

令 $A_i=\{x:a(x)=i\}$ 、 $B_i=\{y:b(y)=i\}$ 。三片输入区域依次是

A_0\times Y,\qquad A_1\times B_0,\qquad A_1\times B_1.

取 $x\in A_1,y\in B_0$ 时，根上的 Alice 结点必走边 $1$ ；Bob 看见前缀 1 后按自己的 $b(y)=0$ 走边 $0$ ，故 transcript 为 10。这一轨迹显示路径不是事后给输入贴的标签，而是双方在每一步仅凭各自视图共同生成的。

若 $a(x),b(y)$ 独立且均为公平比特，这三片叶的概率依次为 $1/2,1/4,1/4$ ，所以最坏长度是 $2$ ，平均长度是 $3/2$ 。信息复杂度沿同一棵树继续计算内部与外部信息成本，并说明为什么输出熵约为 $0.811278$ ，却不能代替消息记录的熵 $1.5$ 。

三个叶串还是 prefix-free 的：没有一个完整 transcript 是另一个的真前缀。否则协议在短串处已经终止，却又要让相同公开对话继续发送，接收方无法知道“沉默”究竟表示结束还是等待。把终止时刻免费编码进时间，会偷偷引入协议树之外的信道。

每一时刻还可以区分双方的本地 view。Alice 的 view 包含 $x$ 、公开 transcript 和她拥有的随机信息，Bob 的 view 则以 $y$ 替代 $x$ ；公开路径相同，不表示两人的私有知识相同。

协议规则必须保证轮到某一方发言时，她的下一步在自己的 view 中已经确定。若树的一条边实际上按对方未发送的输入选择，这棵图即使能为每个完整输入标出正确叶，也不是可执行的通信协议。

不能混合的对象

同一输出标签可能出现在许多叶。各叶输入集分别是矩形，但它们的并通常不是矩形：若两个叶分别含 $(x_0,y_0)$ 与 $(x_1,y_1)$ ，并集未必包含交叉组合 $(x_0,y_1)$ 和 $(x_1,y_0)$ 。因此“都是 0 叶”不能成为无条件合并子树的理由。

另一个容易混淆的对象是“给定 transcript 后输入仍独立”。矩形性质只限制哪些输入可以产生这条对话，并不保证条件概率分解。若原输入分布把质量各半放在 $(0,0)$ 与 $(1,1)$ ，零通信 transcript 对应整个矩形，输入仍然完全相关。若原分布是乘积分布，则条件于任意正质量矩形仍可把双方条件分布相乘；一般相关分布没有这个保证。

一棵随机协议不是单棵确定性协议树。固定所有公共与私有随机币后，才得到一棵树；随机协议整体是这些树的分布。某棵固定树可能在某些输入上出错，只要对每个固定输入，抽到错误树的概率受限即可。把每个输入各自最有利的随机币固定下来，无法得到一棵对所有输入同时正确的树。

密码协议中 transcript 常指承诺、挑战、响应等消息组成的会话记录，分布式系统也会把事件日志叫 transcript。这些用法都强调“一次运行留下的公开序列”，但未必对应本页的逐 bit 二叉树，也未必具有组合矩形性质。术语相同不等于下界工具可以跨模型直接搬用。

树高给出最坏 bit 数，叶深分布则可分析平均通信。若输入服从分布 $\mu$ ，期望深度为 $\mathbb E_{(x,y)\sim\mu}[|\pi(x,y)|]$ ；它可能远低于最大深度。没有声明 $\mu$ 时，不能用“多数路径很短”替代最坏复杂度上界。

推论与应用

协议树把通信下界转成结构计数：成本 $c$ 限制可达叶至多 $2^c$ ，而每片叶又必须是与输出一致的单色矩形。秩、fooling set、矩形 cover 与腐化界等方法，都是用不同证据证明少量这种叶无法组织全部输入。

参考资料

Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Sections 1.1–1.2.
Tim Roughgarden, Communication Complexity (for Algorithm Designers), Lecture 1, Stanford CS369E, 2015；通信策略、本地视图及数据流模拟。
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 1.

形式陈述 ​

树表示的是完整策略 ​

transcript 输入集为何是矩形 ​

一棵三叶协议树 ​

不能混合的对象 ​

反向链接

形式陈述

树表示的是完整策略

transcript 输入集为何是矩形

一棵三叶协议树

不能混合的对象