协议树与通信 transcript

树表示的是完整策略 ​

把一个确定性协议的消息拆成逐 bit 发送，可得到一棵有根二叉树公理库二叉树Binary tree每个节点至多有两个有序子节点的根树。。每个内部结点标记当前发言者；若由 Alice 发言，离开该结点的边由她根据 $x$ 和此前路径选择，若由 Bob 发言则由 $y$ 与此前路径选择。标为 $0$、$1$ 的两条边记录所发 bit，叶结点标记协议输出。

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

$$t=t_1{t}_2\cdots t_k$$

称为该执行的 transcript。它记录实际发生的公开对话，却不包含没有走到的分支，也不等于协议的完整程序。树的最大根叶深度就是逐 bit 口径下的最坏通信量，因此与确定性通信复杂度公理库确定性通信复杂度Deterministic communication complexity在零误差确定性协议中，对所有输入的最坏通信位数取最优所得的复杂度度量。直接对应。

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

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

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

协议树也不要求严格轮流发言。Alice 可以连续发送多个 bit，Bob 也可在自己的阶段连续发言；发言者标签只要求下一边能由该方当前 view 决定。把连续 bit 视为一条长消息只是展示层选择。

一棵三叶协议树 ​

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

$$0,10,11.$$

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

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

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

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

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

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

transcript 输入集为何是矩形 ​

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

由树深归纳，每个结点、特别是每个叶 transcript 的一致输入集，都是组合矩形。若协议正确计算函数 $f$，同一叶上的全部输入还必须具有相同 $f$ 值，因为叶只有一个输出标签。这正是通信矩阵与组合矩形公理库通信矩阵与组合矩形Communication matrix · Combinatorial rectangle将两方函数排成输入行列矩阵，并以行集和列集的笛卡尔积刻画协议能够共同隔离的区域。之间的结构桥梁。

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

不能混合的对象 ​

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

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

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

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

参考资料

• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Sections 1.1–1.2.
• Tim Roughgarden, Communication Complexity (for Algorithm Designers), 2015, Lecture 1.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 1.