布尔查询复杂度度量之间的关系

适用范围与记号 ​

本页默认 $f:\{0,1{\}}^n\to \{0,1\}$ 是 total Boolean function，随机错误取固定常数 $1/3$，写

$$D=D^{\mathrm{query}}(f),R=R_{1/3}^{\mathrm{query}}(f),C=C(f),s=s(f),bs=bs(f),$$

并记实 exact degree 为 $\mathrm{deg}(f)$、$1/3$-近似次数为 $\widetilde{\mathrm{deg}}(f)$。每条边都依赖这组 convention；对 partial function，许多多项式关系会失效或出现指数分离。

直接定义链 ​

最稳固的一组不等式是

$$s\le bs\le C\le D.$$

第一条把敏感单坐标公理库布尔函数敏感度Sensitivity of Boolean functions · Boolean sensitivity统计在固定输入处单独翻转一个坐标会改变函数值的 Hamming 邻居数量。视为单元素敏感块；第二条因为任何证书必须击中每个互不相交敏感块公理库块敏感度Block sensitivity of Boolean functions · Boolean block sensitivity在固定输入处寻找最多个互不相交的坐标块，使整体翻转任一块都会改变函数值。；第三条因为确定性决策树在固定输入上的根叶路径形成证书公理库证书复杂度Certificate complexity of Boolean functions · Boolean certificate complexity用足以强制某个固定输入函数值的最少已知坐标数，分别度量 0-证书与 1-证书。。三步都能逐点证明，再对输入取最大。

随机算法可以忽略随机币，所以同一硬查询 convention 下

$$R\le D.$$

反向不是定义事实。随机树的坏输入可随随机带改变，不能把确定性最坏路径下界直接应用到树的分布。

从证书回到决策树 ​

Total functions 满足

$$D\le C_0(f)C_1(f)\le C^2.$$

算法反复选择一个仍可能的 1-证书并查询其坐标；若证书匹配便输出 $1$，若不匹配则至少消耗当前 0-证书的一项预算。至多 $C_0$ 轮、每轮至多 $C_1$ 次查询。

还存在 total-function 关系

$$C\le b{s}^2,$$

从而证书与块敏感度至多多项式分离。证明需要把最小证书外的坐标组织成敏感块并做 packing，不是 $bs\le C$ 的简单反向；本图记录结论，具体组合证明应单独展开。

多项式两条支路 ​

确定性 $T$-query 树的 1-叶指示多项式次数至多 $T$；随机 $T$-query 算法的接受概率则是次数至多 $T$ 的一致逼近多项式。放宽到近似次数公理库近似次数Approximate degree of Boolean functions · Epsilon-approximate degree在 Boolean cube 上以一致误差 ε 逼近函数所需的最低实多项式次数。只会降低所需次数，而 Nisan–Szegedy 又把块敏感度接回 exact degree。四条关系可合写为

$$\mathrm{deg}(f)\le D,\widetilde{\mathrm{deg}}(f)\le R,\widetilde{\mathrm{deg}}(f)\le \mathrm{deg}(f),bs(f)\le 2\mathrm{deg}(f{)}^2.$$

它把代数相互作用阶数连回局部块翻转。常数依赖 $0/1$ 实多项式 convention；换域或只在 promise 上表示，不能照抄。

随机复杂度与块敏感度 ​

对 total functions，有

$$R=\mathrm{\Omega }(bs).$$

直觉是在达到 $bs(f,x)=k$ 的输入 $x$ 周围，$k$ 个不交敏感块分别产生相反输出。构造在 $x$ 与随机块翻转之间的分布后，低查询算法命中被翻块的概率太小，无法以常数优势区分。互不相交确保一次坐标查询至多直接命中一个块。

该关系隐藏绝对常数，不应写成未经核对的逐点 $R\ge bs$。它也不是说对每个输入都要查询与 $bs(f,x)$ 相同数量；$R$ 和 $bs$ 都先在各自定义中处理最坏输入。

两个校准家族 ​

Parity 是多条边同时取等的锚点：

$$D=R=C=s=bs=\mathrm{deg}=\widetilde{\mathrm{deg}}=n$$

（误差严格小于 $1/2$）。翻任一位都改 parity，任何证书要固定全部位；低次多项式与 parity 的最高阶字符正交，因此近似次数也为 $n$。

对 ${\mathrm{OR}}_n$，有 $D=R=C=s=bs=\mathrm{deg}=n$，但

$${\widetilde{\mathrm{deg}}}_{1/3}({\mathrm{OR}}_n)=\mathrm{\Theta }(\sqrt{n}).$$

因此 approximate degree 给经典随机 OR 下界时只得到平方根量级，并不总是紧；同一个量在量子查询中却更接近真实复杂度。方法下界弱不表示 OR 存在 $O(\sqrt{n})$ 的经典随机算法。

真分离：Rubinstein 型函数 ​

把 $n=k^2$ 个变量分成 $k$ 个大小 $k$ 的块。每块子函数在“恰有一对预先相邻的位置为 $1$、其余为 $0$”时取 $1$，总函数对各块取 OR。在全零输入处，可在每块挑出约 $k/2$ 个互不相交相邻对；翻转任一对都会使函数变 $1$，所以 $bs=\mathrm{\Omega }(k^2)=\mathrm{\Omega }(n)$。

单比特敏感度的最坏值只有 $O(k)$：要么某个块已形成唯一有效对，敏感变化集中在该块；要么翻一位只能影响有限候选对。于是这族函数满足

$$bs(f)=\mathrm{\Theta }(s(f{)}^2),$$

说明 $s\le bs$ 可以有二次级真差距，而不是记号上重复两个局部量。

Partial function 警告 ​

Promise 可以删除连接 total cube 的中间输入，使证书交叉、块翻转和多项式唯一性同时改变。对 partial functions，$D$ 与 $R$ 可出现指数差距，低 approximate degree 也不必由 total-function 多项式链控制其他量。

因此 theorem map 的箭头不能只凭 ID 复用。引用时应写明 total、错误率、查询硬上限、实系数域和 $0/1$ 编码；任何缺项都可能把一条多项式关系错误扩展到 promise 世界。

参考资料

• Noam Nisan, “CREW PRAMs and Decision Trees,” SIAM Journal on Computing 20(6), 1991, pp. 999–1007.
• Noam Nisan and Mario Szegedy, “On the Degree of Boolean Functions as Real Polynomials,” Computational Complexity 4, 1994, pp. 301–313.
• Harry Buhrman and Ronald de Wolf, “Complexity Measures and Decision Tree Complexity: A Survey,” Theoretical Computer Science 288(1), 2002, pp. 21–43.
• David Rubinstein, “Sensitivity vs. Block Sensitivity of Boolean Functions,” Combinatorica 15, 1995, pp. 297–299.