确定性与随机查询复杂度

形式陈述

确定性复杂度

设 $f:S\to\{0,1\}$ ，其中 $S\subseteq\{0,1\}^n$ 。对确定性坐标查询算法 $A$ ，记 $q_A(x)$ 为输入 $x$ 上读取的坐标数。确定性查询复杂度定义为

D^{\mathrm{query}}(f) =\min_{A\text{ 正确计算 }f}\ \max_{x\in S}q_A(x).

这就是计算 $f$ 的最浅确定性查询决策树深度。算法必须在每个合法输入上零误差正确；同一叶所包含的 promise 输入因而都具有相同函数值。上标 $\mathrm{query}$ 用来区别通信复杂度中也常简写为 $D(f)$ 的度量。

定义先对输入取最坏情形，再对算法取最优。某个输入存在一条很短的证书，不表示算法预先知道该走哪条路径；它仍要通过查询确认当前输入确实具备那份证书。

两类随机查询复杂度

随机算法可写成 $A(x;R)$ 。固定随机带 $r$ 后，它是一棵确定性决策树；随机性选择树，错误模型决定哪些算法合格，成本量词则决定这些执行怎样计费。

零误差随机复杂度 $R^{\mathrm{query}}_0(f)$ 要求每次终止时都输出正确值，常用 Las Vegas 口径

R^{\mathrm{query}}_0(f) =\inf_A\ \max_{x\in S} \mathbb E_R[q_A(x;R)].

期望只对内部随机性取，最坏输入仍在外层。若某文献另要求每条随机带都有查询硬上限，应把该上限单独报告；有限期望不排除小概率长路径。

对 $0<\varepsilon<1/2$ ，有界误差复杂度 $R^{\mathrm{query}}_\varepsilon(f)$ 要求每个固定 $x\in S$ 都满足

\Pr_R[A(x;R)=f(x)]\ge1-\varepsilon.

本页采用每次执行至多 $T$ 次查询的硬上限，并在合法算法中最小化 $T$ 。也有人用 $\max_x\mathbb E_R[q_A(x;R)]$ 定义 expected-cost bounded error；比较数值前必须对齐约定，不能因记号相同就视为同一量。

若三种复杂度都用每次执行的硬上限计费，允许算法忽略随机币会给出

R^{\mathrm{query}}_\varepsilon(f) \le R^{\mathrm{query}}_0(f) \le D^{\mathrm{query}}(f)

但本页给 $R_0$ 采用的是期望成本，不能把这条链原样与其混用。当前约定下仍有 $R^{\mathrm{query}}_0(f)\le D^{\mathrm{query}}(f)$ ；若一个零误差算法的最坏输入期望查询数为 $c$ ，在 $3c$ 次查询处截断并任意输出，由 Markov 不等式可得错误至多 $1/3$ 的硬上限算法。因此可比较的结论是 $R^{\mathrm{query}}_{1/3}(f)\le3R^{\mathrm{query}}_0(f)$ ，而非未经常数转换的裸不等式。

直觉

确定性算法沿一棵固定决策树前进；随机算法先用内部随机性选择查询策略，再在固定输入上运行。随机性能够让不同执行查看不同坐标，却没有改变信息边界：未查询的位置仍不可见，成功概率也必须对每个合法输入分别成立。因而复杂度比较既要说明错误是否允许，也要说明成本取硬上限还是对随机币取期望。

Promise 的作用是排除难以区分的输入带。若两类合法输入在许多坐标上形成常数密度差，随机抽样就能迅速看到信号；若它们只差一个未知 bit，抽样必须覆盖近乎全部位置。随机优势来自问题结构提供的可见统计间隔，不是“用了概率”本身。

例子与边界

Promise approximate majority

考虑偏函数 $\operatorname{GapMaj}_n$ ：当 Hamming 重量 $|x|\le n/3$ 时输出 $0$ ，当 $|x|\ge2n/3$ 时输出 $1$ ，中间输入不在 promise 中。算法独立均匀抽取 $t$ 个坐标（允许重复），查询这些 bit，并令经验均值

\widehat p=\frac1t\sum_{j=1}^t x_{I_j}.

若 $\widehat p\ge1/2$ 就输出 $1$ ，否则输出 $0$ 。对低重量输入，真实均值 $p\le1/3$ ；只有经验均值向上偏至少 $1/6$ 才会出错。对高重量输入同理需要向下偏至少 $1/6$ 。Hoeffding 界给出每个合法输入上的错误概率

\Pr[\text{错误}] \le \exp\!\left(-2t\left(\frac16\right)^2\right) =e^{-t/18}.

因此取 $t\ge18\ln(1/\delta)$ ，便以至多 $t$ 次查询把错误控制到 $\delta$ 。查询数与 $n$ 无关，但这一优势完全依赖两类输入之间的常数 gap；算法承诺的不是精确恢复 $|x|$ ，而是区分 promise 两侧。

这条轨迹还把概率量词写清了。输入 $x$ 先固定，随机坐标 $I_1,\ldots,I_t$ 后抽取；每个合法 $x$ 都分别满足误差界。若先随机抽输入再报告平均成功率，可能把某一整类难输入埋在低概率区域，不符合 bounded-error 查询复杂度。

没有 gap 时抽样会失败

对 total 函数 $\operatorname{OR}_n$ ，输入可能是 $0^n$ ，也可能只有一个未知位置为 $1$ 。均匀抽 $t$ 个坐标时，后一输入中的唯一 $1$ 被全部漏掉的概率为

\left(1-\frac1n\right)^t.

当 $t=o(n)$ 时，这个概率接近 $1$ ，所以 approximate-majority 的常数样本分析不能搬到 OR。把 promise 中的“至少 $n/3$ 个差异”换成“至少一个差异”，不是换一个数字的同类例子，而是消除了产生随机优势的信息密度条件。

零误差也不能靠“没抽到 $1$ ”提前宣布 OR 为 $0$ ：任何未查询位置仍可能藏有 $1$ 。随机查询顺序可以改变不同输入上的期望停止时间，但在全零输入上必须读完全部坐标。正确性结构和成本平均方式需要分别分析。

推论与应用

下界的量词边界

确定性叶数或对手论证通常只证明每一棵确定性树都有某个坏输入。随机算法是树的分布，而不同树的坏输入可以不同；让对手先看见随机带再选择输入，会证明一个更强、却未必与标准模型相同的结论。随机下界常需构造一个固定困难输入分布，再证明每棵低查询确定性树在该分布下平均错误大。

随机重复也不是免费的。将常数错误降到 $\delta$ 通常需要 $O(\log(1/\delta))$ 个独立副本，并按多数或适合错误结构的规则聚合；查询数随之增长。复用同一随机坐标集合不会自动获得独立失败事件。

最后，total 与 partial Boolean functions 的关系可能不同。任何变换输入的下界证明都要确认新输入仍在 promise 域中；任何抽样上界都要说明 promise 如何保证被检测结构拥有足够密度。省略定义域，复杂度符号就失去可复核的对象。

查询复杂度可以继续连接证书复杂度、块敏感度与多项式下界方法。前两者刻画局部见证与成块扰动，后者还通向量子查询下界；这些关系在 total 与 partial functions 上可能不同，也不能跨成本口径无条件套用。

参考资料

Harry Buhrman and Ronald de Wolf, “Complexity Measures and Decision Tree Complexity: A Survey,” Theoretical Computer Science 288(1), 2002, pp. 21–43.
László Lovász, Moni Naor, Ilan Newman, and Avi Wigderson, “Search Problems in the Decision Tree Model,” SIAM Journal on Discrete Mathematics 8(1), 1995, pp. 119–132.
Stasys Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012, Chapter 14.

形式陈述 ​

确定性复杂度 ​

两类随机查询复杂度 ​

Promise approximate majority ​

没有 gap 时抽样会失败 ​