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

形式陈述

适用范围与记号

本页默认 $f:\{0,1\}^n\to\{0,1\}$ 是 total Boolean function，在确定性与随机查询复杂度中把随机错误固定为 $1/3$ ，写

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

并记实精确多项式次数为 $\deg(f)$ 、 $1/3$ -近似次数为 $\widetilde{\deg}(f)$ 。常函数的这些量均约定为零，空输出侧的证书最大值也取零。以下关系均依赖这组约定；对 partial function，许多多项式关系会失效或出现指数分离。

直接定义链

最稳固的一组不等式是

s\le bs\le C\le D.

第一条把敏感单坐标视为单元素敏感块；第二条因为任何证书必须击中每个互不相交敏感块；第三条因为确定性决策树在固定输入上的根叶路径形成证书。三步都能逐点证明，再对输入取最大。

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

R\le D.

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

从证书回到决策树

Total functions 满足

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

算法在当前限制后的函数尚未确定时，选择一个仍可能的 1-证书并查询其坐标。若匹配便输出 $1$ ；否则，每个仍可能的 0-输入的证书都与所选 1-证书在某个冲突坐标相交。该坐标现在已固定，可从余下证书中删除，因此当前子函数的 $C_0$ 至少下降一。至多 $C_0(f)$ 轮，每轮至多查询 $C_1(f)$ 个新坐标；若函数提前变为常量则立即结束。

还存在 total-function 关系

C\le bs^2,

从而证书与块敏感度至多多项式分离。这里有一段简短的完整证明。固定输入 $x$ ，选一族不能再添加成员的两两不交、包含意义下极小的敏感块 $B_1,\ldots,B_r$ 。对每个 $B_j$ ，在输入 $y=x^{\oplus B_j}$ 上翻回任意 $i\in B_j$ 都会恢复 $f(x)$ ，否则 $B_j\setminus\{i\}$ 仍敏感，违反极小性。所以 $|B_j|\le s(f)$ 。

这些块的并集固定为 $x$ 上的值后必为证书：若仍有相反输出的补全，其与 $x$ 不同的坐标全在并集外，从中又能取出一个极小敏感块，违反不可再添加性。于是

C(f,x)\le\sum_{j=1}^r|B_j| \le bs(f,x)s(f), \qquad C(f)\le bs(f)s(f)\le bs(f)^2.

这里的 packing 只需不能再添加成员，不要求先求出最大块数。全函数条件保证上述逐位翻回的中间输入都合法。

多项式两条支路

查询多项式方法给出确定性 $T$ -query 树的 1-叶指示多项式次数至多 $T$ ；随机 $T$ -query 算法的接受概率则是次数至多 $T$ 的一致逼近多项式。放宽到近似次数只会降低所需次数，而 Nisan–Szegedy 又把块敏感度接回 exact degree。四条关系可合写为

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

它把代数相互作用阶数连回局部块翻转。这里保留 Nisan–Szegedy 的经典保守常数，不声称最优；换域或只在 promise 上表示，不能照抄。

还应补上敏感度的反向控制。Huang 在 2019 年证明，对全布尔函数，

\deg(f)\le s(f)^2.

结合前面的保守界便有 $bs(f)\le2s(f)^4$ ，从而敏感度也能以多项式控制这些组合度量。这一定理解决了敏感度猜想，补齐了从敏感度控制其他组合度量的方向。Huang 原文，Theorem 1.4

随机复杂度与块敏感度

对 total functions，有

R=\Omega(bs).

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

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

直觉

这些度量从不同角度观察同一棵 Boolean 决策树。Sensitivity 看单边翻转，block sensitivity 允许成块扰动，certificate 记录确认当前值所需固定的坐标， $D$ 与 $R$ 衡量算法实际访问，而 exact/approximate degree 把接受行为投影到代数表示。箭头成立，是因为一种证据能被转换成另一种；它们并不是同一概念换了记号。

关系图最有价值之处在于暴露可迁移下界的路径，也暴露路径在哪里失真。例如 $\widetilde{\deg}\le R$ 允许用近似次数下界随机查询，却不保证紧； $C\le bs^2$ 说明 total function 上两者至多多项式分离，却依赖 cube 的完整中间输入。每条边都携带自己的模型条件。

例子与边界

两个校准家族

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

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

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

对 $\operatorname{OR}_n$ ，有 $D=C=s=bs=\deg=n$ ，而 $R=\Theta(n)$ ，并非一般精确等于 $n$ 。例如均匀选取 $\lceil n/2\rceil$ 个坐标，见到 $1$ 就接受，否则以概率 $1/3$ 接受。全零输入的错误为 $1/3$ ；任何非零输入漏掉全部 $1$ 的概率至多 $1/2$ ，再乘上拒绝概率 $2/3$ ，错误也至多 $1/3$ 。对 $n\ge2$ ，这给出严格少于 $n$ 次的硬查询上界。另一方面

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

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

真分离：Rubinstein 型函数

取偶数 $k\ge2$ ，把 $n=k^2$ 个变量分成 $k$ 个大小 $k$ 的块。每块固定不交位置对 $(1,2),(3,4),\ldots,(k-1,k)$ ；子函数在恰有其中一对为 $1$ 、其余为 $0$ 时取 $1$ ，总函数对各块取 OR。在全零输入处，每块的 $k/2$ 个位置对都是两两不交的敏感块；翻转任一对都会使函数变 $1$ ，所以 $bs=\Omega(k^2)=\Omega(n)$ 。

若只有一个块有效，恰有该块的 $k$ 次单比特翻转会使总输出变零；若至少两个块有效，则没有敏感单比特。若所有块都无效，每个块至多有一个单比特翻转能使其变为一个有效位置对，所以总敏感度至多 $k$ 。因此 $s(f)=k$ ，而 $k^2/2\le bs(f)\le k^2$ ，从而这族函数满足

bs(f)=\Theta(s(f)^2),

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

Partial function 警告

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

因此，这些关系必须连同各自的前提一起使用。引用时应写明 total、错误率、查询硬上限、实系数域和 $0/1$ 编码；任何缺项都可能把一条多项式关系错误扩展到 promise 世界。

推论与应用

对 total Boolean functions，这些边把表面不同的复杂度压在多项式范围内： $s\le bs\le C\le D$ ， $D\le C^2$ ， $C\le bs^2$ ，且 $bs\le2\deg^2$ 、 $\deg\le s^2$ 。已知其中一个量的下界或上界时，可以沿方向传播，但每经过一次平方都会损失强度，最终结论未必紧。

Parity、OR 与 Rubinstein 型函数分别承担三种校准：全部相等、代数下界明显偏弱、局部量发生真实二次分离。新结论若与这些家族冲突，通常意味着箭头方向、错误模型或 total/partial 条件被误读；它们比抽象记忆不等式更可靠地检验推理。

参考资料

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.
Hao Huang, “Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture,” Annals of Mathematics 190, 2019, pp. 949–955，Theorem 1.4。

形式陈述 ​

适用范围与记号 ​

直接定义链 ​

从证书回到决策树 ​

多项式两条支路 ​

随机复杂度与块敏感度 ​

两个校准家族 ​

真分离：Rubinstein 型函数 ​

Partial function 警告 ​