同时消息传递模型

SMP 把交互压成两份彼此看不见的摘要。Alice 无法根据 Bob 的消息补充缺失信息，Bob 也无法对 Alice 提问；referee 得到两份独立生成的视图后，必须一次性完成拼接。困难不只在消息短，还在发送者没有协调反馈。

公共币能在发信前对齐摘要坐标，使两条消息虽然独立计算，却可被 referee 逐项比较。私有币下的随机选择彼此隐藏，referee 若不知道两个摘要使用了什么共同基准，就只能从消息分布本身恢复关系；Equality 的平方根分离正体现协调成本。

SMP 中两方各向裁判发送一条消息且彼此不可见；单向通信复杂度理路单向通信复杂度One-way communication complexity限制 Alice 只向 Bob 发送一次消息，由 Bob 结合自身输入输出，并按消息 bit 数衡量代价。中 Alice 直接把消息发给持有另一半输入的 Bob。裁判是否拥有输入、是否共享随机性以及消息能否依赖接收方身份，都会改变复杂度。

公共币 Equality 指纹 ​

对 $n\ge 1$、$x,y\in \{0,1{\}}^n$ 的Equality理路Equality 通信问题Equality communication problem · EQ communication problem比较双方 n-bit 私有串是否完全相同，展示确定性完整传输与公共随机指纹之间的指数差异。，公共串给出独立均匀向量 $r^{(1)},\dots ,r^{(k)}$。Alice 发送

Bob 同时发送 $b_j=⟨r^{(j)},y⟩mod2$。Referee 接受当且仅当每个 $a_j=b_j$。

若 $x=y$，两条消息逐位相同，必然接受。若 $x\ne y$，每个内积指纹碰撞概率为 $1/2$，$k$ 次独立碰撞概率为 $2^{-k}$。两位发送者各发 $k$ bit，总通信 $2k$，不需要任何交互。

这条协议与单向 Equality 的指纹公式相似，但信息流不同：Bob 不负责计算输出，也看不到 Alice 消息；只有 referee 汇合两份摘要。把 referee 偷换成 Bob 会改变谁拥有 $y$、谁看见公共串以及通信计数。

Private coin 的真实差距 ​

没有共享随机性时，双方无法免费选择同一个随机线性函数。经典结果表明，private-coin classical SMP 对 Equality 达到任意固定 $0<\epsilon <1/2$ 的错误率需要 $\mathrm{\Theta }(\sqrt{n})$ bit，而 public-coin SMP 只需常数通信（对固定错误）。

一种上界使用组合块码理路信道码Channel code把消息映为信道输入码字并从带噪输出恢复消息的编码—译码对。，先用常率、常数相对距离的二进码编码输入，把长度 $O(n)$ 的码字补零到最近的平方数长度，再排成边长 $O(\sqrt{n})$ 的方阵；补零只改变常数比例的相对距离。Alice 私下抽一列并发送列内容及编号，Bob 独立抽一行并发送行内容及编号；referee 检查交点。相等时必一致，不同时随机交点以常数概率落在差异位置，常数次独立重复给出常数错误。编号的 $O(\log n)$ 成本已包含在 $O(\sqrt{n})$ 内。下界则限制独立消息能保留的区分信息；完整论证见 Gavinsky–Regev–de Wolf §3。

与交互和协调器模型的边界 ​

任意 SMP 协议都可由一般交互协议模拟：双方把消息发到其中一方或中央节点。但交互协议的第二条消息可以依赖第一条，SMP 不允许这种反馈，所以交互下界不能自动由 SMP 下界替代。

Coordinator 模型允许多位玩家与中心往返多轮；SMP referee 只被动收一次消息。若 referee 可以发挑战再收回复，模型已经接近 star-topology 交互通信。

消息长度之外还要声明消息是否量子、是否共享纠缠以及 referee 的测量。经典 private/public SMP 的结论不能直接套到量子通信理路量子通信复杂度Quantum communication complexity允许双方交换量子寄存器并选择是否预共享纠缠，以 qubit 数、经典 bit 数和错误概率共同衡量协议。。

最后，消息统计相关不等于输入统计相关。即使输入独立，公共币也能让消息相关；即使输入高度相关，private-coin 消息在给定完整输入后仍由独立私有币生成。下界证明必须条件化正确的变量。

SMP 是分布式 sketch 与一次性汇报系统的自然抽象：各数据源在看不到其他摘要时向中心发送消息，中心统一判定。迁移协议时应保留总消息或最大单消息口径、共享随机性的可见者以及 referee 是否拥有额外输入。

它也提供一条清晰的模型层级：一般交互可模拟 SMP，而 SMP 不能利用反馈；public-coin 可协调哈希，private-coin 不具备这一免费资源；量子消息与共享纠缠又形成另一层能力。下界只会沿“强模型下界推出弱模型下界”的方向安全传播。