证书复杂度

证书回答“已经知道哪些坐标以后，相反输出便不再可能”，却不支付寻找这些坐标的成本。正、负输入需要排除的替代输入不同，因此 0-证书与 1-证书可能极不对称；确定性决策树的每条正确根叶路径则自动交付当前输入的一份证书。

OR 的两侧不对称 ​

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

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

这解释了“找到一个见证”和“确认不存在见证”的查询差异。证书大小按最有利的局部事实集计，不包含算法寻找那个 $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)$。对输入取最大、再对算法最小化，得到基本下界

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

Total function 的乘积上界 ​

对 total Boolean function 还有经典关系

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

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

这个交叉论证也适用于整个有限乘积域 ${\mathrm{\Sigma }}^n$：若一份 0-证书与一份 1-证书没有冲突坐标，就能把两份一致的局部赋值合并并补全为同一个输入，与它们强制相反输出矛盾。限制已查坐标后，剩余域仍是完整乘积，所以上述乘积上界同样成立。对偏函数，合并后的赋值可能落在 promise 域之外；证书因而未必有这一交叉性质，不能直接套用该上界。

与 NP 证书的边界 ​

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

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

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