非确定性通信复杂度

形式陈述

存在证书的量词

设 $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-输入面对每份证书都至少有一方拒绝。证书可以因输入而异，却不能在双方验证过程中根据未公开信息临时改写。

本文按固定长度二进制证书的位数计费，记最小长度为 $N^1(f)$ ，双方在本地分别输出验证结果。若另计最后交换的验证 bit，复杂度只增加 $O(1)$ 。

固定证书产生 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\max\{1,C^1(f)\}\right\rceil.

当 $C^1(f)=0$ 时，函数恒为零，双方直接拒绝即可，证书长度为零。一般情形下，同一个 1-输入可有多份证书，矩形也可重叠：cover 对应“至少有一份证书成功”，不要求形成唯一分区。

直觉

确定性协议必须由双方自己找到一条正确路径，非确定性协议则允许全知证明者指出“该看哪一份证据”，但不能替双方完成不可验证的推理。证书之所以有用，是因为同一个编号把全局 yes 主张拆成 Alice 与 Bob 各自能核对的局部条件；可靠性要求任何 no 输入都无法伪造一份让两边同时通过的编号。

矩形 cover 正好刻画这种存在量词。每个证书覆盖一块可分别验证的 1-输入，多个块可以重叠，也无需形成唯一分区。证书长度只负责指出覆盖块，因此是块数的对数；如何在没有证明者时自行找到正确块，则不在非确定性模型的承诺内。

例子与边界

交集非空的见证

设 $n\ge1$ ，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$ ，不能只看问题名称。

co-nondeterministic 对照

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

对 Equality， $x\ne y$ 可用证书 $(i,b)$ 指定不同坐标及其方向：Alice 检查 $x_i=b$ ，Bob 检查 $y_i=1-b$ ，共需 $\lceil\log_2 n\rceil+1$ bit。只有索引还不够让两人分别验证两个值确实不同； $x=y$ 的 1-证书则不能只指出一个相同坐标，因为其他位置仍可能不同。两侧复杂度可以相差很大，因此写“非确定性复杂度”时应标明是在证明哪个输出。

存在证书与随机抽样

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

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

确定性双方还需要通过交互找到能确定答案的区域。矩形 cover 给出了哪些编号可以证明答案，但如何在不知道对方输入时找到合适编号，仍是额外的搜索任务。

推论与应用

非确定性通信把证书设计问题转成单色矩形覆盖问题：构造短证书等价于给出小 cover，证明证书下界则要排除用少量同色矩形覆盖目标输出层。Fooling set 等工具正是通过限制每块矩形能容纳的关键点来完成后一种证明。

参考资料

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.

形式陈述 ​

存在证书的量词 ​

固定证书产生 1-矩形 ​

交集非空的见证 ​

co-nondeterministic 对照 ​