证书复杂度

固定输入的局部证明 ​

设 $f:S\to \{0,1\}$，$S\subseteq \{0,1{\}}^n$，固定合法输入 $x\in S$。坐标集 $I\subseteq [n]$ 是 $x$ 的证书，若每个与 $x$ 在 $I$ 上一致的合法输入都具有相同函数值：

$$\mathrm{\forall }y\in S,(y_I=x_I)⟹f(y)=f(x).$$

证书复杂度 $C(f,x)$ 是最小 $|I|$。它不是算法额外收到的字符串，而是“如果已经知道这些输入坐标，就足以排除相反输出”的最小局部事实集合。

按输出分层定义

$$C_b(f)=\underset{x\in S:f(x)=b}{max}C(f,x),b\in \{0,1\},$$

以及 $C(f)=max\{C_0(f),C_1(f)\}$。若某一输出在 promise 域中没有输入，相应最大值需按约定省略或取 $0$；比较定理前应排除这种常值退化。

证书包含坐标和值。对固定 $x$，值由 $x_I$ 已确定，所以常只记坐标集；脱离 $x$ 后只给 $I$ 并不能说明要验证哪种局部赋值。

OR 的两侧不对称 ​

对 ${\mathrm{OR}}_n$，任何含至少一个 $1$ 的输入都有大小 $1$ 的 1-证书：指出一个满足 $x_i=1$ 的坐标，所有与它一致的输入都输出 $1$。因此

$$C_1({\mathrm{OR}}_n)=1.$$

全零输入要证明输出 $0$，必须固定全部 $n$ 个坐标。若遗漏位置 $j$，把该位改为 $1$ 的输入仍与已知坐标一致，却使 OR 变为 $1$。故

$$C_0({\mathrm{OR}}_n)=n,C({\mathrm{OR}}_n)=n.$$

这解释了“找到一个见证”和“确认不存在见证”的查询差异。证书大小按最有利的局部事实集计，不包含算法寻找那个 $1$ 付出的查询；在最坏输入上，算法仍可能查看全部坐标。

决策树路径给出证书 ​

任取正确确定性查询决策树公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。，固定输入 $x$。根叶路径上被查询的坐标集 $I_x$ 一定是 $x$ 的证书：若某个合法 $y$ 在这些坐标上与 $x$ 一致，它会沿完全相同的答案边到达同一叶，因此 $f(y)=f(x)$。

于是对每个 $x$ 都有 $C(f,x)\le q_A(x)$。对输入取最大、再对算法最小化，得到基本下界

$$C(f)\le D^{\mathrm{query}}(f).$$

这个方向不要求 total function；promise 输入只需沿路径保持在 $S$ 中。它也没有说最小证书可以被算法预先知道，因而不能反向推出 $D(f)\le C(f)$。

Total function 的乘积上界 ​

对 total Boolean function 还有经典关系

$$D^{\mathrm{query}}(f)\le C_0(f)C_1(f).$$

递归算法在当前限制下若函数未定，选一个仍合法的 1-输入及其大小至多 $C_1(f)$ 的 1-证书，查询证书全部坐标。若答案全匹配就输出 $1$；若出现不匹配，进入相应限制后的子函数并重复。

每次不匹配都会使当前子函数的 0-证书复杂度至少下降 $1$。理由是当前选出的 1-证书必须与每个 0-证书在某个取值冲突的坐标相交；查询并走入不匹配分支后，该冲突坐标已固定，可从后续 0-证书预算中删除。因此至多经历 $C_0(f)$ 轮，每轮查询至多 $C_1(f)$ 个坐标。

证明使用全 cube 上的 total 性；对偏函数，证书可能因 promise 缺口而不再拥有同样的交叉性质，乘积上界不能不经检查直接搬用。

与 NP 证书的边界 ​

NP 证书是额外 witness 字符串，其长度按编码 bit 计，验证器还可计算复杂关系。本页证书只揭示原输入的若干坐标，大小按查询位置数计；它更接近决策树叶上的 partial assignment。

一个坐标若存放 $w$ bit word，揭示它一次在 word-query 模型算一个查询，却含 $w$ bit 信息。把坐标证书大小当作普通证明 bit 长，会忽略访问单元宽度。

随机算法的低错误查询也不保证每条执行路径形成零误差证书；错误叶可能同时容纳两种函数值。证书与随机复杂度的进一步关系需要额外论证，不能只把期望路径长度代入确定性不等式。

参考资料

• Harry Buhrman and Ronald de Wolf, “Complexity Measures and Decision Tree Complexity: A Survey,” Theoretical Computer Science 288(1), 2002, pp. 21–43.
• Stasys Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012, Chapter 14.
• Ryan O'Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014, Chapter 2.