Set Disjointness 通信问题

形式陈述

输入、表示与输出

固定宇宙 $[n]=\{1,\ldots,n\}$ 。Alice 持有 $A\subseteq[n]$ ，Bob 持有 $B\subseteq[n]$ ，定义

\operatorname{DISJ}_n(A,B) =\mathbf1[A\cap B=\varnothing].

本页约定“不交”输出 $1$ ，“有交点”输出 $0$ ；有些文献采用相反编码，引用证书或单侧错误结论时必须先翻转对应输出。集合以 $n$ -bit 特征向量表示，通信按 bit 计，而不是把一个任意大集合当作一个消息对象。

集合运算给出抽象交集，两方通信问题还加入私有输入划分。若双方都看到两集合，求交只是本地计算；困难来自没有一方能直接读取另一集合。

确定性协议与下界

Alice 可发送 $A$ 的 $n$ -bit 特征向量，Bob 与自己的向量逐位 AND。若只由 Bob 输出，通信为 $n$ bit；若要求公开叶标签，Bob 再发送结果，总计 $n+1$ bit。

公开输出的下界可由1-fooling set 完整得到。对每个 $S\subseteq[n]$ ，取输入对

(S,\overline S), \qquad \overline S=[n]\setminus S.

两集合显然不交，所以全部 $2^n$ 个点输出 $1$ 。若 $S\ne T$ ，不可能同时有 $S\subseteq T$ 与 $T\subseteq S$ ；因此至少一个差集 $S\setminus T$ 或 $T\setminus S$ 非空。前者使交叉输入 $(S,\overline T)$ 有交点，后者使 $(T,\overline S)$ 有交点，至少一个交叉值为 $0$ 。

故这 $2^n$ 个 1-输入必须落入不同 1-叶。问题还存在 0-输入，至少再需一个 0-叶；深度至多 $n$ 的树只有 $2^n$ 个叶，不够容纳它们。于是公开输出 convention 下

D^{\mathrm{cc}}(\operatorname{DISJ}_n)=n+1.

Bob-only 版本的上下界相差至多最后一 bit；标准渐近写法为 $\Theta(n)$ 。这里精确的 $n+1$ 等式假设 $n\ge1$ ；若宇宙为空，函数恒为 $1$ ，零通信即可。

随机复杂度的已知状态

对任意固定常数 $0<\varepsilon<1/2$ ，即使允许公共随机币、双侧错误和任意多轮交互，也有随机线性下界

R^{\mathrm{cc}}_\varepsilon(\operatorname{DISJ}_n)=\Theta(n).

上界直接来自确定性特征向量协议。 $\Omega(n)$ 下界不是上述 fooling-set 证明自动给出的：随机协议允许每个固定输入在少量随机树上出错，关键点不再逐棵树全部占据正确单色叶。完整随机下界需要控制带错误的大矩形或 transcript 泄露，属于单独的证明任务。

直觉

Equality 只需确认两份长对象是否完全相同，随机投影很容易让任意固定差分显形；Disjointness 却要确认所有 $n$ 个坐标都没有共同的 $1$ 。潜在交点可以藏在任一坐标，不同集合对又呈现不同局部结构，常数长度指纹无法同时排除这些可能。

确定性 fooling set 把每个集合 $S$ 与其补集配成一个 disjoint 对。任意两对交叉后，包含关系不可能双向成立，于是至少产生一个交点；这迫使所有关键 yes 输入分居不同叶。随机协议能容忍少量错叶，必须由更强的 corruption 或信息复杂度论证恢复线性障碍。

例子与边界

一个真实执行轨迹

取 $n=8$ ，Alice 持有 $A=\{2,5,8\}$ ，Bob 持有 $B=\{1,5,7\}$ 。Alice 的特征向量按坐标 $1$ 到 $8$ 为 01001001。Bob 收到后与自己的 10001010 逐位比较，在坐标 $5$ 同时看到 $1$ ，因此输出 $0$ 。

Alice 与 Bob 的八位特征向量在坐标五同时为一，因此集合有交点且 DISJ 输出零 — Set Disjointness 的共同坐标

若 Bob 改持 $B'=\{1,3,7\}$ ，同一 Alice 消息与 10100010 没有共同的 $1$ ，输出 $1$ 。协议发送完整向量，不会因实际交点很早出现就节省最坏通信；要利用实例结构提前停止，需要交互式地安排查询或发送稀疏表示，并重新计算最坏编码长度。

Promise 与相邻问题

集合大小可能被限制为恰好 $k$ ，交集大小可能 promise 为 $0$ 或 $1$ ，也可能要求输出 $|A\cap B|$ 或找出交点。这些版本有不同参数和下界；结论应写成关于宇宙大小 $n$ 、集合稀疏度 $k$ 和错误率的陈述。

“图不交”可能指两张图的边集是否相交，也可能指图中是否存在顶点不交路径；它们不是默认的 $\operatorname{DISJ}_n$ 。流式版本还需说明元素到达顺序和是否允许 turnstile 更新。只复用 Disjointness 名称，不能把这些模型参数带过来。

非确定性方向也依输出编码而变。证明有交点只需给一个元素作为短证书；证明完全不交却没有同样直接的局部 witness。若本页把不交编码为 $1$ ，短交点证书描述的是 $0$ -侧，而不是 $N^1$ 。

推论与应用

这个线性结论是通信复杂度最常用的硬核之一。它表明随机哈希能极大改善 Equality，却不能把任意两集合的不交性压成常数通信；两个问题输出同为一 bit，输入信息结构却不同。

归约中的角色

数据流下界常把 Alice 的集合元素作为流前缀、Bob 的元素作为后缀，使目标统计量区分是否存在共同元素。若 streaming 状态只有 $S$ bit，切分处状态就形成一条 $S$ -bit 消息；随机 DISJ 线性下界随后排除过小空间。

例如把 $A$ 中每个元素插入一次，再把 $B$ 中每个元素插入一次。对非空流，最大频率 $F_\infty$ 在不交时恰为 $1$ ，有交时恰为 $2$ 。因此精确求最大频率的算法能直接判定 DISJ；若算法只返回满足 $(1-\rho)F_\infty\le\widehat F_\infty\le(1+\rho)F_\infty$ 的估计，两个输出区间只有在 $1+\rho<2(1-\rho)$ ，即 $\rho<1/3$ 时才严格分开。空流可以用“没有元素”的状态单独处理。

这个计算也说明不能把精确流下界随意说成任意近似下界：当 $\rho=1/3$ 时两个区间在 $4/3$ 接触，同一个合法估计可能来自两种答案，原阈值归约已经失效。类似思想可进入 sketch、数据结构和分布式聚合，但每个归约都要明确 pass 数对应多少轮、更新顺序是否允许删除、错误事件是否保持，以及输出阈值怎样区分两类集合。通信下界归约范式负责组织这些接口。

参考资料

Tim Roughgarden, “Lower Bounds for One-Way Communication: Disjointness, Index, and Gap-Hamming”, Stanford CS369E Lecture 2, 2015；DISJ 与最大频率的数据流归约。
Bala Kalyanasundaram and Georg Schnitger, “The Probabilistic Communication Complexity of Set Intersection,” SIAM Journal on Discrete Mathematics 5(4), 1992, pp. 545–557.
Alexander A. Razborov, “On the Distributional Complexity of Disjointness,” Theoretical Computer Science 106(2), 1992, pp. 385–390.
Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapters 4–5.

形式陈述 ​

输入、表示与输出 ​

确定性协议与下界 ​

随机复杂度的已知状态 ​

一个真实执行轨迹 ​

Promise 与相邻问题 ​

归约中的角色 ​

反向链接