第十一章：查询复杂度

查询模型将输入视为 oracle。算法可以选择读取哪些位置，本地计算免费；复杂度只统计查询次数。该模型直接刻画“必须观察多少输入信息”。

Decision tree

对 Boolean function

$$f:\{0,1\}^n\to\{0,1\},$$

确定性 decision tree 的内部节点查询某个 $x_i$，两条边对应 0/1，叶节点输出答案。最坏深度最小值记为 $D(f)$。

例如：

$$D(\mathrm{OR}_n)=n.$$

在全零输入上，若少查询一个位置，该位置改为 1 后 transcript 不变，算法会输出相同答案，因此必须查询全部位置。

Certificate complexity

对输入 $x$，certificate 是一组位置及其值，使所有与该部分赋值一致的输入都具有相同函数值。最小大小记为 $C(f,x)$，再定义

$$C_0(f)=\max_{f(x)=0}C(f,x),\qquad C_1(f)=\max_{f(x)=1}C(f,x).$$

对 OR：

$$C_1(\mathrm{OR})=1,\qquad C_0(\mathrm{OR})=n.$$

certificate 描述验证固定答案所需信息，decision tree 则必须在不知道答案和 certificate 位置时寻找它。

Sensitivity 与 block sensitivity

sensitivity $s(f,x)$ 统计翻转单个 bit 会改变输出的位置数。block sensitivity 允许翻转互不相交的 bit block，记为 $bs(f,x)$。

这些 measure 与 decision tree、certificate degree 等存在多项式关系。曾经的 sensitivity conjecture 询问 $bs(f)$ 是否由 $s(f)$ 的多项式控制，现已得到肯定解决。

复杂度 measure 之间的关系用于转移 lower bound：若证明某个较易分析的 measure 很大，即可推出 decision tree lower bound。

Randomized query

随机 decision tree 对每个输入以高概率输出正确答案，复杂度记为 $R_\varepsilon(f)$。对 OR，随机抽样无法在最坏输入上区分“全零”与“唯一一个 1 且位置未知”，因此有界错误仍需

$$R(\mathrm{OR}_n)=\Theta(n).$$

Yao principle 允许选择分布：例如一半概率为全零，一半概率在均匀随机位置放一个 1。查询 $o(n)$ 次的确定性算法以常数概率看不到该 1。

Adversary argument

确定性 adversary 在回答查询时保持多个不同答案的输入仍与 transcript 一致。只要 yes/no 候选同时存在，算法不能终止。

更一般的 relation/adversary method 为候选输入对赋权，分析一次查询最多消除多少权重。该方法在经典与量子查询 lower bound 中都有对应形式。

Polynomial method

深度 $T$ 的确定性 decision tree 可以表示为次数至多 $T$ 的 multilinear polynomial。随机算法的接受概率也是次数至多 $T$ 的多项式。

因此，若任何近似 $f$ 的实多项式都需要次数至少 $d$，则

$$R(f)=\Omega(d).$$

量子 $T$ 次查询算法的接受概率是次数至多 $2T$ 的多项式，因此 approximate degree 同样给出 quantum query lower bound。

Property testing

property testing 不要求精确计算函数，而是在 oracle 输入上区分：

• 输入具有性质 $\mathcal P$；
• 输入与任何具有 $\mathcal P$ 的对象距离至少 $\varepsilon$。

距离通常按需要修改的输入比例定义。算法复杂度可以只依赖 $\varepsilon$，与输入规模无关或次线性。

例如测试图或函数的局部结构时，只采样少量位置。promise 中的距离间隙使次线性算法成为可能；若必须区分只差一个 bit 的输入，通常仍需线性查询。

Adaptive 与 non-adaptive

adaptive query 的下一个位置依赖此前回答；non-adaptive 算法一次确定全部查询。自适应性可能降低查询数，但增加轮数和并行延迟。

分析结果应同时说明：

• 查询总数；
• adaptive rounds；
• one-sided 或 two-sided error；
• oracle 返回值大小；
• promise 与距离度量。

Cell-probe model

data structure lower bound 常使用 cell-probe model。预处理把数据写入若干 $w$-bit cell；查询算法的计算免费，只统计访问 cell 次数。

该模型比 word-RAM 更强，因此 cell-probe lower bound 能排除更广泛的数据结构。证明常结合通信复杂度、信息转移和 chronogram。

本章自测

1. OR 在全零输入上为什么需要查询全部位置？
2. certificate complexity 与 decision tree complexity 分别量化什么？
3. Yao 分布如何证明 randomized OR lower bound？
4. polynomial degree 为什么可以限制查询次数？
5. property testing 的距离 promise 为什么是次线性查询的基础？

上一章：通信复杂度 · 下一章：量子计算 →