非确定性通信复杂度

存在证书的量词

设 $f:X\times Y\to\{0,1\}$ 。非确定性 1-协议允许一个知道完整 $(x,y)$ 的证明者给 Alice 与 Bob 同一份证书 $w$ 。双方分别用自己的输入、证书和协议公开信息验证。完备性与可靠性为

\begin{aligned} f(x,y)=1&\Longrightarrow \exists w\;[A(x,w)=B(y,w)=1],\\ f(x,y)=0&\Longrightarrow \forall w\;[A(x,w)B(y,w)=0]. \end{aligned}

第一行只要求 1-输入有一份能让双方都接受的证书；第二行要求 0-输入面对每份证书都至少有一方拒绝。证书可以因输入而异，却不能在双方验证过程中根据未公开信息临时改写。

以最坏合法证书的 bit 长度计费，得到 $N^1(f)$ 。不同文献会把双方最后交换验证 bit 计入常数，或把猜测写成非确定性协议树；这些 convention 至多带来 $O(1)$ 差异，渐近结论应同时说明采用哪种验证接口。

固定证书 $w$ ，令

A_w=\{x:A(x,w)=1\},\qquad B_w=\{y:B(y,w)=1\}.

双方都接受的输入集恰为 $A_w\times B_w$ ，是一个组合矩形。可靠性保证该矩形只含 $1$ -输入；完备性保证所有 $1$ -输入至少落入某个证书矩形。因此全部证书产生一个覆盖 $f^{-1}(1)$ 的 1-单色矩形 cover。

反过来，给定 $k$ 个 1-单色矩形 $A_j\times B_j$ 覆盖全部 1-输入，证明者发送编号 $j$ 。Alice 检查 $x\in A_j$ ，Bob 检查 $y\in B_j$ 。1-输入至少有一个覆盖块可被接受，0-输入不属于任何 1-单色矩形，所以每个编号都被至少一方拒绝。

若 $C^1(f)$ 表示最小 1-单色矩形 cover 大小，这一对应给出

N^1(f)=\left\lceil\log_2 C^1(f)\right\rceil

在“只计证书编号、双方本地给 accept bit”的 convention 下成立。这里是 cover 而不是 partition：同一个 1-输入可有多份证书，矩形也可重叠；非确定性正是允许从多条接受路径中存在一条成功路径。

Alice 与 Bob 分别持有 $A,B\subseteq[n]$ ，考虑函数

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

若交集非空，证明者发送一个元素 $i\in A\cap B$ 的索引。Alice 检查 $i\in A$ ，Bob 检查 $i\in B$ ；两者都通过便接受。证书长度为 $\lceil\log_2 n\rceil$ bit。

例如 $A=\{2,5,8\}$ 、 $B=\{1,5,7\}$ 时，证书 $i=5$ 在两边都能本地验证。若集合不交，无论证明者发哪个 $i$ ，至少一方的成员检查失败。证书不是“相信有人说它们相交”，而是把全局主张压成双方可分别核对的同一个局部对象。

这个例子与集合不交问题的 yes/no convention 相反：若把 DISJ=1 定义为交集为空，那么短证书证明的是 0-输入，属于 co-nondeterministic 一侧。输出编码的选择会交换 $N^1$ 与 $N^0$ ，不能只看问题名称。

$N^0(f)$ 用 0-单色矩形 cover 或 0-输入证书定义，等价于 $N^1(1-f)$ 。它要求每个 0-输入存在可验证证书，而每个 1-输入没有任何证书能让双方同时接受。

对 Equality， $x\ne y$ 可以用一个不同坐标作为短 0-证书； $x=y$ 的 1-证书则不能只指出一个相同坐标，因为其他位置仍可能不同。两侧复杂度可以相差很大，因此写“非确定性复杂度”时应标明是在证明哪个输出。

随机协议对每个输入从一个概率分布抽随机币，并要求大多数随机选择正确；非确定性协议只要求 yes 输入存在一份好证书，完全不关心从所有 bit 串中随机抽到它的概率。一个证书可能在指数多候选中独一无二，仍是合法的短非确定性证明。

同样，证明者的猜测不是共享公共随机串。公共随机性必须独立于输入产生，不能编码只对当前 $(x,y)$ 有效的交点；非确定性证明者恰恰可以看完整输入，但受到“no 输入无证书能骗过双方”的可靠性限制。

最后，短 cover 不能直接给确定性低通信协议。确定性双方必须唯一确定落入哪个矩形，而 cover 允许大量重叠；从“存在一个合适编号”变成“在不知道对方输入时找到编号”正是额外困难。

参考资料

Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapter 2.
Juraj Hromkovič, Communication Complexity and Parallel Computing, Springer, 1997, Chapters 2–3.
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 2.