多方通信复杂度

两方模型只需回答“谁知道哪一半”，多方模型还必须描述知识怎样重叠、消息怎样扩散。Blackboard 上的一 bit 像写在公共白板上，所有人同时获得；点对点网络中的同一事实却可能需要沿多条边复制。输入完全相同，换一张通信图就可能改变总成本与瓶颈玩家。

NIH 与 NOF 则改变了通信开始前的知识缺口。NIH 每位玩家只握住自己的拼图，NOF 每位玩家恰好缺一块却看到其余全部。后者的大量重叠有时能让少数消息补齐共同答案，但这种优势取决于函数如何使用各输入块，不能脱离具体编码比较。

Parity 的 NIH 与 NOF 执行 ​

在 NIH 中，$k$ 位玩家各持一个 bit $x_i$，要公开输出 parity $x_1\oplus \cdots \oplus x_k$。Blackboard 上让前 $k-1$ 位依次写出自己的 bit，最后一位写出总 parity，共 $k$ bit；若只让最后一位本地输出，可省最后回传 bit。输入只有一 bit 不让总通信变成常数独立于 $k$，因为每位玩家的 bit 都可能翻转答案。

对三位 NOF 玩家，玩家 1 看到 $(x_2,x_3)$，可写 $x_2\oplus x_3$；玩家 2 看到 $x_1$，再写 $x_1$。所有人由两 bit transcript 得到总 parity。这个执行展示重叠视野如何省消息，却不证明每个 NOF 问题都严格更容易；两种模型没有脱离输入重编码的逐问题简单包含关系。

多方Set Disjointness公理库Set Disjointness 通信问题Set Disjointness communication problem · DISJ communication problem判断双方私有集合是否没有共同元素的典型两方问题，其随机线性下界支撑大量空间与分布式下界。 ​

在 NIH 版本中，每位玩家持有 $S_i\subseteq [n]$，常见目标判断

朴素 blackboard 协议让每位玩家写出 $n$-bit 特征向量，再本地求逐位 AND，总通信 $kn$ bit。稀疏集合可发送元素列表，但成本变成 $O(\sum _i|S_i|\log n)$，并非无条件更小。

另一些文献把“集合不交”定义为任意两个集合都不相交，或让宇宙元素按玩家分块；这些任务的 yes/no 结构不同。引用多方 Disjointness 下界前，必须写清是共同交集为空还是 pairwise disjoint。

失败边界 ​

Blackboard 的一 bit 被所有人同时看见，点对点网络中向 $k-1$ 人广播可能要发送多份。以“写一次”计费的上界不能原样搬到 message-passing 总通信。

轮数也会改变能力。Simultaneous 模型每位玩家只向 referee 发一次消息，多方交互则允许根据早期消息协调；二者都叫 multiparty，却不能共用未注明轮数的复杂度。

最后，NOF 玩家看见“其他全部输入”不等于有一个中央 referee 看见全部输入。每个玩家仍缺一块，不同缺口如何交叠正是模型结构。

与两方归约 ​

把 $k$ 位玩家分成两组，并让每组内部免费共享输入，可把多方协议压成两方协议，从而继承某些下界。但分组会改变各方可见信息和每轮哪些消息跨 cut；只有跨组 bit 才成为两方通信。

反方向把两方输入复制给许多玩家，可能产生额外共享信息，不能默认保持困难。有效归约需要逐玩家列出视野，并证明模拟不让任何一方看到原模型中不可见的数据。

多方通信下界常被转译为分布式监控、并行查询与流式空间下界。转译时除了总 bit，还要保留玩家数、拓扑、轮数、每方输入分布与输出位置；遗漏其中一项，就可能把 blackboard 的共享优势或 coordinator 的中心知识误带入目标系统。