确定性与随机查询复杂度

确定性复杂度 ​

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

$$D^{\mathrm{query}}(f)=\underset{A\text{ 正确计算 }f}{min}\underset{x\in S}{max}{q}_A(x).$$

这就是计算 $f$ 的最浅确定性查询决策树公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。深度。算法必须在每个合法输入上零误差正确；同一叶所包含的 promise 输入因而都具有相同函数值。上标 $\mathrm{query}$ 用来区别通信复杂度中也常简写为 $D(f)$ 的度量。

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

两类随机查询复杂度 ​

随机算法可写成 $A(x;R)$。固定随机带 $r$ 后，它是一棵确定性决策树；随机性选择树，却不会让算法看见未查询 bit。不同错误模型要使用不同的成本量词。

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

$$R_0^{\mathrm{query}}(f)=\underset{A}{inf}\underset{x\in S}{max}{\mathbb{E}}_R[q_A(x;R)].$$

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

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

$${\text{Pr}}_R[A(x;R)=f(x)]\ge 1-\epsilon .$$

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

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

$$R_{\epsilon }^{\mathrm{query}}(f)\le R_0^{\mathrm{query}}(f)\le D^{\mathrm{query}}(f)$$

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

Promise approximate majority ​

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

$$\hat{p}=\frac{1}{t}\sum _{j=1}^t{x}_{I_j}.$$

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

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

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

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

没有 gap 时抽样会失败 ​

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

$${(1-\frac{1}{n})}^t.$$

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

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

下界的量词边界 ​

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

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

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

参考资料

• 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.