跳转到内容
← 返回计算理论
计算理论当代约 20 分钟阅读

Yao 1979：分布式计算的复杂度问题怎样把通信写成资源

Some Complexity Questions Related to Distributive Computing

Yao通信复杂度STOC 1979双方协议相等性

1979 年 4 月 30 日至 5 月 2 日，第十一届 ACM 计算理论年会（STOC）在佐治亚州亚特兰大举行。斯坦福大学的姚期智（Andrew Chi-Chih Yao）发表《Some Complexity Questions Related to Distributive Computing (Preliminary Report)》，页码 209 至 213。DOI 为 10.1145/800135.804414。标题用的是 distributive，不是后来更常见的 distributed。本页的对象是这份已发表的五页初步报告：把布尔函数 $f(i,j)$ 的输入劈成两半，一人只知道 $i$、一人只知道 $j$，双方轮流各送一比特，计量单位从此变成「跨过这条缝必须说多少话」。确定性协议、随机化协议、识别函数（相等性），以及把随机下界收成最坏输入分布上的确定性期望，都落在同一枚钉子上。

它不是 通信复杂度 的学科总览。总览页管矩形覆盖、集合不相交、流算法与电路深度；那些工具大多是后十年才钉死的。它不是 姚期智 的人物页，不是 1977 年 FOCS 那篇把极小极大写成算法度量的论文，更不是 1982 年的百万富翁问题或 1986 年的混淆电路。后两篇属于安全计算，封面不同。它不是 分布式计算理论 里兰波特式的时钟与共识，不是 计算复杂性 的 $P$ 对 $NP$ 地图，不是 电路复杂度 总览，也不是概率可验证明。本页不把协议写成窃听、比对口令或拆系统的步骤。

破除误解：通信复杂度不是网络课，也不是已经写好的指纹公式

第一层误解把标题听成网络协议，或听成「两台机器怎样同步、怎样处理丢包」。原文抽象掉延迟、带宽与故障。双方被假定拥有无限的局部算力，唯一被计数的是彼此交换的比特。正因为算力被拿掉，测到的困难才纯粹来自输入被切开。若即使无限算力也必须传送 $k$ 比特，任何真实系统都逃不掉这条界：它不依赖 $P$ 是否等于 $NP$，也不依赖单向函数。把 1979 年收进套接字手册，会把一条资源定义说成工程实现。把无限算力听成「于是没有难度」，则说反了设定：免费的是本地计算，昂贵的是跨缝的那几比特。

第二层误解把教材里的标准句提前写进这五页：「姚期智已经证明 $n$ 比特串的相等性确定性要 $n$ 比特、随机化只要 O(log⁡n)O(\log n)，并且用多项式指纹写好了上界。」原文的识别函数（identification function）写在下标集合 {0,1,…,n−1}\{0,1,\ldots,n-1\} 上：f(i,j)=δijf(i,j)=\delta_{ij}，即 $i=j$ 时为 1、否则为 0。P1P_1 发送 $i$ 的二进制，长度 ⌈log⁡2n⌉\lceil\log_2 n\rceil，已经够 P2P_2 判定。这与后来把输入改写成 $n$ 比特串、把论域放大到 2n2^n 的相等性是同一函数的两种标尺：串长 $n$ 的相等，就是大小为 2n2^n 的识别。随机指纹把串版本压到对数比特，是模型被算清之后的标准上界，不是这五页里印好的求值公式。把后来的教具读回初步报告，会把一次模型定义收成一部习题集。

第三层误解把极小极大听成 1979 年才发明的博弈论，或听成「随机等于平均」。精确陈述来自冯·诺依曼；算法侧的写法是姚期智 1977 年 FOCS《Probabilistic Computations: Toward a Unified Measure of Complexity》。1979 年换的是被计量的资源：代价不再是步数，而是协议送出的比特。把 1977 年的引理与 1979 年的资源叠成同一篇论文，会把两年的钉子焊死成一页。

第四层误解把对象听成密码攻击或香农信道课。识别函数问的是两人能否确认同一个下标，不是从对话里还原口令。香农处理带噪声的大量单向传输；这里是单次、无噪声、最坏情况的交互。百万富翁与混淆电路是邻居，封面是安全求值，不是最短对话。

双方协议、识别函数，以及把随机收成最坏分布

装置从一张有限表开始。设 M={0,1,…,m−1}M=\{0,1,\ldots,m-1\}，N={0,1,…,n−1}N=\{0,1,\ldots,n-1\}，布尔函数 f:M×N→{0,1}f:M\times N\to\{0,1\}。P1P_1 只知道整数 i∈Mi\in M，P2P_2 只知道整数 j∈Nj\in N。两人按事先约定的算法轮流发送比特，每次一比特，直到能够共同确定 $f(i,j)$。算法必须对每一个对 $(i,j)$ 都给出正确答案；复杂度取最坏情况下交换的比特数，再对算法取最小。后来通行的记号把这台最小值写成 $D(f)$ 或 $C(f)$。原文给的第一个算术例子是 f(i,j)=(i+j) mod 2f(i,j)=(i+j)\bmod 2：P1P_1 送出 $i$ 的奇偶性这一比特，P2P_2 即可算出，再少则不可能。奇偶性之所以够用，是因为函数只依赖和的奇偶，不依赖 $i$ 的其余比特。识别函数则相反：对角线上的每一个 $i$ 都必须与别的 $i'$ 分开，少说一句就会把某两个下标叠进同一段对话。

这是阿贝尔森（Harold Abelson）1978 年 FOCS 模型的组合变体。阿贝尔森处理光滑实值函数，两个处理器各自握有一部分实变元，允许互送光滑函数值，界来自分析。姚期智把函数收成布尔、把报文收成比特；当 m=2sm=2^s、n=2tn=2^t 时，两边握的就是布尔串。分析味道被换成组合味道。输入从此是表上的一个格子，协议是两人合作读出格子里的 0 或 1。算力无限，意味着两人都可以任意计算自己该送哪一比特；他们不能做的只有一件事：看见对方手里的那一个整数。

单向复杂度 C(f;1→2)C(f;1\to 2) 是同篇报告里的另一根尺子：P1P_1 一次性把一串比特送给 P2P_2，此后不再回话，P2P_2 独自输出 $f(i,j)$。平凡上界是 P1P_1 发送 $i$ 的二进制，至多 ⌈log⁡2m⌉\lceil\log_2 m\rceil 比特。若两行完全相同，也就是对一切 $j$ 都有 $f(i,j)=f(i',j)$，则这两行不必区分，P1P_1 只需说出自己落在哪一种行类型里。因而单向复杂度由互不相同的行数决定，而不是由 $m$ 本身决定。识别函数的 $n$ 行是标准基，彼此不同，单向就是 ⌈log⁡2n⌉\lceil\log_2 n\rceil。相对互素判定 $f(i,j)=1$ 当且仅当 gcd⁡(i,j)=1\gcd(i,j)=1，以及序关系 $i<j$，被原文列为另外两个例子。它们证明这张表不必来自「人为设计的谜题」：数论与排序里已经有劈成两半的自然函数。相对互素后来才被算出更精细的随机界，不是这五页的定理。

双方协议比单向多出的那一点自由，是可以追问。P2P_2 先回一比特，等于把列集合切成两半；P1P_1 再根据自己所在的行决定下一刀。原文用平面 $k$ 分解抓住一类有几何的表：若干「行区间 ×\times 列区间」矩形盖住函数为 1 的格子。定理 2 证明，一旦存在平面 $k$ 分解（$k>1$），双方通信可以被压到 O(log⁡k)O(\log k)，上界写成以 $4/3$ 为底的对数加常数；每一刀用一比特声明输入落在哪一侧区间。单向则不超过 $k$，因为直接发送矩形编号即可。一般组合矩形没有左右顺序，原文给出与分解数成近似线性再乘对数的上界。把任意矩形划分都收成 O(log⁡2χ)O(\log^2\chi) 是阿霍、乌尔曼与扬纳卡基斯 1983 年的后话。推论转向典型函数：几乎所有 n×nn\times n 布尔函数的分解数大于 $n/4$，因而单向复杂度大于 log⁡2n−4\log_2 n-4，贴着发送下标的平凡上界。识别函数不是「几乎所有函数」：对角线上 $n$ 个 1，平面分解的 $k$ 就是 $n$，对数比特既够用也几乎必要。

识别函数把确定性的账写死。论域是 $[n]$ 时，D=Θ(log⁡n)D=\Theta(\log n)。把每个下标改写成 $n$ 比特串，论域变成 2n2^n，$D$ 变成 Θ(n)\Theta(n)。两种写法是同一枚钉子的两种刻度。确定性协议若少送一比特，就会有两个不同的对角输入 $(x,x)$ 与 $(x',x')$ 走出同一段对话；那段对话对应的输入集合必须是一行子集与一列子集的乘积，也就是后来所称的组合矩形。矩形里若同时装下两个对角点，则混杂对 $(x,x')$ 也被装进去，而 $f(x,x')=0$，协议无法对整个矩形给出同一个正确答案。因此对角线上的 $n$ 个（或 2n2^n 个）点两两不能共处一块「输出为相等」的单色矩形。矩形数目至少这么大，对话长度至少是它的对数。这就是愚人集论证在识别函数上的原形状。原文用分解数说话，后来教材把同一件事画成矩阵上的单色矩形。画法是教具，对象是：一段对话所能确认的输入集合，必须是乘积集。

随机化把同一枚钉子掰开。允许双方抛硬币、允许以小概率说错之后，识别不再被迫把整个下标送过去。标准手续是指纹：随机抽一个探针，只送取值；两个不同对象碰撞的概率可被压到任意小，对 $n$ 比特串通信是 O(log⁡n)O(\log n)。$n$ 对 log⁡n\log n 的落差，是随机性作为资源的一次可检验定价。手续属于 随机算法 后来写进教科书的那一页，不是初步报告里的编号定理。原文把概率手续写成同一模型的变体，并点出更弱的同时消息通道：双方不交谈，只各自向看不见输入的裁判送一份报文。识别函数在这条通道上的随机复杂度被写成待回答的问题；纽曼与塞格迪 1996 年、巴巴伊与基梅尔 1997 年才钉上平方根量级。把指纹或同时消息的答案提前写进初步报告，会把问题收成解答。

分布复杂度是随机下界的工作台。固定分布 μ\mu，问有没有短的确定性协议，使错误只发生在 μ\mu 的一小部分质量上。姚氏原理说：公开硬币随机协议的最坏代价，等于最难的那个 μ\mu 上的分布代价。一边是协议设计者抛硬币，一边是对手挑输入分布，均衡处两个数字相等。1977 年把这条等式写在一般算法上；1979 年让等式里的代价变成跨缝比特。于是「证明随机通信下界」不必分析所有硬币，只需构造一个毒分布。识别函数在均匀分布下并不毒：随机指纹的期望已经短。不相交函数后来才提供真正毒的分布，随机性几乎省不下渐近通信。何种函数对硬币敏感，是此后四十年的分类学，不是这五页的清单。本页提供的是资源与那条把随机收成分布的杠杆。

乘积集、平面分解与极小极大回答的是对话能切出什么、区间表为何能收到对数、随机下界为何可以改写成找一个分布。三句都不是操作单。

它证明了什么，没有覆盖什么

它证明了：可以把「两人各握一半输入、合作计算布尔函数」写成一种复杂度。被计量的是比特，不是步数。单向与双方是两根尺子；平面 $k$ 分解把有区间几何的表收到 O(log⁡k)O(\log k) 双方通信，而几乎所有表的单向复杂度贴着 log⁡n\log n。识别函数是动机：确定性一侧，发送下标既够用也几乎必要。它还把概率手续与同时消息放进同一模型，使「随机能否少说话」成为可检验的问题，而不是口号。用后来的语言，这就是通信复杂度作为资源的原句。无条件下界在 计算复杂性 里极为稀有；这条资源后来向流空间、数据结构与电路深度输出了一批这样的下界，那是总览页的地图，不是 1979 年已经铺好的公路。

它没有证明集合不相交的随机线性下界。那是 1992 年才钉死的主定理。它没有证明对数秩猜想，没有写出卡奇默–维格森博弈，也没有把芯片面积—时间权衡收成定理——汤普森 1979 年的 VLSI 论证是同时代邻居。它没有给出 $n$ 比特相等性的指纹作为编号算法，也没有解决同时消息上识别函数的随机复杂度。它更没有触及 $P$ 对 $NP$。通信下界可以对具体函数无条件成立，并不蕴含时间类的分离。库克一九七一年论文 问的是多项式时间完全性；本页问的是跨缝比特。

它没有覆盖百万富翁、混淆电路或单向函数。那些论文计量的是安全，不是最短对话。密码学基础 需要的平均情况困难，也不能从识别函数的最坏情况通信下界偷运过去。相对互素与序关系在原文里是例子，不是已完成的复杂度表。一般矩形划分的平方对数上界、公开硬币与私有硬币、量子比特，都不在这五页里。工业网络能缩短许多平均对话，并不把最坏情况的矩阵作废。本页不说明如何监听对话或把相等性检查改成攻击步骤。

跨域连接

  • 通信复杂度：总览页把矩形、不相交、流内存与电路深度收成一张学科地图；本页只提供地图上的第一枚钉子。钉子的形状是双方轮流送比特、单向与平面分解，不是后来才成为主定理的不相交线性下界。把两页叠在一起读，才能看见：资源先作为「跨缝必须说多少话」出现，再被用来给别的模型做转换器。地图可以后写；钉子的金属成分以 1979 年的表与协议为准。
  • 计算复杂性：时间类计量步数，空间类计量格子，本页计量跨越一条割的比特。三类资源可以写在同一张地图上，分离的逻辑不同。$P$ 对 $NP$ 仍开放，识别函数的确定性通信却已经有无条件的对数（或线性，取决于论域刻度）下界。把通信下界听成已经分开 $P$ 与 $NP$，会把一种不依赖计算假设的界收成一种最著名的开放问题。库克钉子问完全性；本页钉子问割。
  • 随机算法：1977 年的极小极大把随机最坏期望写成最坏分布上的确定性期望；1979 年让期望里的数字变成比特。识别函数是随机性指数级有用的样本：确定性必须说全，随机只需探针。硬币在这里不是把误差藏进工程容差，而是一种被定价的资源。把指纹听成「碰巧猜对」，会把可放大的碰撞概率说成运气。毒分布则给出相反样本：有的函数，硬币几乎买不来更短的对话。
  • 可计算性：停机问题把「有没有手续」写成不可判定。本页假定手续存在，并且局部算力不受限。两人各自都能算任意可计算函数，仍然可能必须送很多比特，因为谁也看不见对方的输入。可判定与多项式可判定是两层边界；可计算与可短对话又是一层。把识别听成不可判定，会把资源问题收成存在问题。对角化在无界时间里分开递归与递归可枚举；在这张有限表上，困难来自乘积结构，不来自自指。
  • 证明：一段合法对话是关于 $f(i,j)$ 的交互证据：成绩单必须在对应矩形上单色。证书是这条成绩单，不是整张表。必然相对于事先固定的协议，只覆盖所切出的乘积集。随机协议把必然改成高概率。
  • 科学哲学：通信复杂度是可检验的关系：存在或不存在某种长度的协议。证伪一条下界需要的是对所有输入都更短且错误可控的协议，不是又一次碰巧很短的对话。先有被切开的布尔表，后有别的模型把切缝翻译过去。

参考文献

  • Andrew Chi-Chih Yao, "Some Complexity Questions Related to Distributive Computing (Preliminary Report)", Proceedings of the 11th Annual ACM Symposium on Theory of Computing, Atlanta, 1979, pp. 209–213. DOI: 10.1145/800135.804414. —— 本文对象：双方比特协议、单向复杂度、平面分解、识别函数，以及把通信写成资源。
  • Harold Abelson, "Lower Bounds on Information Transfer in Distributed Computations", Proceedings of the 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, 1978, pp. 151–158. —— 论文点名的分析型前辈：光滑函数与光滑报文，用以标明布尔比特模型是变体不是抄袭。
  • Andrew C. Yao, "Probabilistic Computations: Toward a Unified Measure of Complexity", Proceedings of the 18th Annual Symposium on Foundations of Computer Science, 1977, pp. 222–227. DOI: 10.1109/SFCS.1977.24. —— 极小极大在算法侧的出处，用以标明分布复杂度的博弈论杠杆早于 1979 年的通信资源。
  • Alfred V. Aho, Jeffrey D. Ullman & Mihalis Yannakakis, "On Notions of Information Transfer in VLSI Circuits", Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 133–139. DOI: 10.1145/800061.808742. —— 一般矩形划分的平方对数上界，用以标明口径收紧不是 1979 年的定理。
  • Ilan Newman & Mario Szegedy, "Public vs. Private Coin Flips in One Round Communication Games", Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 561–570. DOI: 10.1145/237814.238005. —— 同时消息上相等性随机复杂度的关键上界之一，用以标明姚期智留下的问题不是初步报告里的已解定理。
  • László Babai & Peter G. Kimmel, "Randomized Simultaneous Messages: Solution of a Problem of Yao", Proceedings of the 12th Annual IEEE Conference on Computational Complexity, 1997, pp. 239–246. DOI: 10.1109/CCC.1997.612319. —— 把同时消息随机复杂度与确定性复杂度的平方根关系写清，用以标明 1979 年的 oblivious 变体被回答的年份。

延伸阅读

正文中引用本条 · 4