Set Disjointness 通信问题

输入、表示与输出 ​

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

$${\mathrm{DISJ}}_n(A,B)=\mathbf{1}[A\cap B=\varnothing ].$$

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

集合运算公理库集合运算Set operations · Union, intersection, difference并、交、差与补集等按成员条件构造新集合的运算。给出抽象交集，通信问题还加入私有输入划分。若双方都看到两集合，求交只是本地计算；困难来自没有一方能直接读取另一集合。

确定性协议与下界 ​

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

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

$$(S,\bar{S}),\bar{S}=[n]\setminus S.$$

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

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

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

Bob-only 版本的上下界相差至多最后一 bit；标准渐近写法为 $\mathrm{\Theta }(n)$。

一个真实执行轨迹 ​

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

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

随机复杂度的已知状态 ​

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

$$R_{\epsilon }^{\mathrm{cc}}({\mathrm{DISJ}}_n)=\mathrm{\Theta }(n).$$

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

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

归约中的角色 ​

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

类似思想可进入 sketch、数据结构和分布式聚合，但每个归约都要明确 pass 数对应多少轮、更新顺序是否允许删除、错误事件是否保持，以及输出阈值怎样区分两类集合。通信下界归约范式公理库通信下界归约范式Communication lower-bound reduction pattern · Communication reduction for lower bounds将受限算法的执行切成双方可本地模拟的片段，把跨切口状态或访存内容变成消息并保留全部参数。负责组织这些接口。

Promise 与相邻问题 ​

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

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

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

参考资料

• 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.