确定性与随机查询复杂度

Yao 原理怎样把分布困难转成随机下界 ​

后面的奇偶性证明将展示一个常用套路。选定输入分布 $\mu$，并证明每棵深度小于 $T$ 的确定性决策树，在 $\mu$ 下的平均错误都大于 $\epsilon$。那么任何由这些树随机混合而成的算法，其平均错误也大于 $\epsilon$，自然不可能对每个输入都达到错误率至多 $\epsilon$。

反过来说，若一个随机算法对每个输入的错误率至多为 $\epsilon$，则在任意固定 $\mu$ 下平均错误也至多为 $\epsilon$；对随机带再平均，必存在一条固定随机带，使对应确定性树的分布错误至多为 $\epsilon$。

这就是 Yao 极小极大原理理路Yao 极小极大原理Yao minimax principle · Yao principle · Yao's principle在有限输入与固定资源预算下，把最坏输入随机算法的最小损失等同于最难输入分布上的确定性最小平均损失。用于查询下界的基本方向。它把“对抗所有随机策略”转成“寻找一个能难住所有小确定性树的分布”。完整的极小极大等式还要明确策略空间及成本形式；尤其期望成本版本不能不加修改地沿用硬深度论证。

证明时应始终让困难分布先于随机带选定。根据算法本次随机选择临时改变输入，证明的是更强的对手模型，而不一定是原来的随机查询模型。

随机性显著有效：有间隔的多数问题 ​

令 $n=3m$、$m\ge 1$，承诺输入中 $1$ 的个数满足二者之一：

算法只需区分这两种情况。在中间区间上没有正确性要求。

随机算法均匀、有放回地抽查 $q$ 个位置，计算样本中 $1$ 的比例 $\hat{p}$；当 $\hat{p}\ge 1/2$ 时输出高密度，否则输出低密度。对任一固定合法输入，抽样结果是均值 $p=|x|/n$ 的独立 Bernoulli 变量，而 $p$ 与阈值 $1/2$ 的距离至少为 $1/6$。

由 Hoeffding 不等式理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。，任一方向的错误概率至多为

这里指数使用自然底数，故写作 $q=\lceil 18\ln \left(1/\delta \right)\rceil$ 就保证错误率至多为 $\delta$，与 $n$ 无关。若预算超过 $n$，直接读完整个输入即可；缓存重复位置不会破坏基于独立抽样索引的概率分析。

确定性算法却需要恰好 $2m+1$ 次查询。上界是一直查询，直到见到 $m+1$ 个相同的比特：若是 $1$，低密度承诺不可能；若是 $0$，高密度承诺不可能。最多看 $2m+1$ 位就必有一种比特出现 $m+1$ 次。

下界可以由对抗回答看出：在前 $2m$ 次查询中交替返回零和一，使已见到的两类比特都不超过 $m$。特别在查询了 $2m$ 位后，已见 $m$ 个零与 $m$ 个一，未读的 $m$ 位全填零或全填一，分别产生两种合法输入，而且此前所有回答完全相同。算法仍无法确定输出。

于是

随机性在这里利用了“全局密度有固定间隔”。它并没有高概率读到所有重要位置，而是让少量样本代表整体密度。

随机性只能改善常数：OR 的完整下界 ​

考虑

确定性算法在全零输入上必须看完全部位置，因此 $D({\mathrm{OR}}_n)=n$。随机算法也不能用常数次查询区分全零与只有一个隐藏 $1$ 的输入。

要证明这对任意自适应算法都成立，而不只是对均匀抽样成立，可以比较 $0^n$ 与 $e_i$，其中 $e_i$ 只有第 $i$ 位为一。令 $p_i$ 为算法在全零输入上查询过第 $i$ 位的概率。

用同一条随机带耦合两次执行。在查询第 $i$ 位之前，两份输入给出完全相同的回答，所以算法行动也相同。若始终没有查询它，两次输出必定一致。因此两份输入上“输出一”的概率之差至多为 $p_i$。

若错误率至多为 $\epsilon <1/2$，全零输入输出一的概率至多为 $\epsilon$，而 $e_i$ 上至少为 $1-\epsilon$，于是

对所有位置求和，左边恰好是全零输入上查询的不同位置数的期望。若每次执行至多查询 $T$ 位，则

所以 $R_{1/3}({\mathrm{OR}}_n)=\mathrm{\Theta }(n)$。零错误时，同一论证令 $\epsilon =0$，说明全零输入上几乎必然查询每个位置，故 $R_0({\mathrm{OR}}_n)=n$。

与有间隔多数问题相比，OR 的否定答案必须排除一个可能极稀疏的见证；不存在保证见证占常数比例的承诺。这正是两个问题对随机性反应不同的原因。

连常数都不能省：奇偶性 ​

令 ${\mathrm{PARITY}}_n(x)=\sum _i{x}_{i}mod2$。在均匀输入分布下，一个查询少于 $n$ 位的确定性决策树，到任何可达叶子时仍至少有一位未读。条件于已见答案，未读位仍均匀，因此最终奇偶性为零或一的概率各为 $1/2$。

于是任何深度小于 $n$ 的确定性树，在这个分布下都恰好有 $1/2$ 错误；这些树的任何随机混合也一样。一个对每个输入都保证错误率小于 $1/2$ 的随机算法，不可能具有小于 $n$ 的统一查询上限。因此

这个精确等式依赖硬预算。若改计最坏输入上的期望查询，算法可以以概率 $1-2\epsilon$ 读取全部 $n$ 位并正确输出，以概率 $2\epsilon$ 零查询并抛公平硬币。每个输入上的错误恰为 $\epsilon$，期望查询却只有 $(1-2\epsilon )n$。少于 $n$ 的是平均成本；其中仍有完整读取 $n$ 位的执行，因此并不反驳硬预算结论。

这里的信息障碍与 OR 又不相同：OR 隐藏一个可能存在的见证，而奇偶性的每一个未读位都能直接翻转答案。

错误放大与模型边界 ​

若一个算法错误率至多为 $1/3$，独立重复并对输出取多数，可以用 $O(\log \left(1/\delta \right))$ 倍查询预算把错误降到 $\delta$。重复之间必须使用独立随机性；输入始终是同一个固定对象。对固定常数错误率，复杂度通常因此只差常数因子。

查询复杂度本身不衡量选取下一位置所需的计算量，也不自动反映实际缓存、网络时延或批量读性能。若一次接口返回一个机器字、一个邻接表条目或一段区间，计费单位已经改变，不能直接与单比特查询比较。

量子查询还允许对索引作相干叠加访问，经典的“读过哪些确定位置”论证不再直接适用。本条目的结论应放在 经典查询模型理路查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。中理解，量子版本需另用相应的算法与下界方法。

从查询例子到结构下界 ​

三个例子对应不同的信息需求：有间隔多数允许用样本估计整体，OR 要搜索稀疏见证，奇偶性要求消除每个未读位的不确定性。性质测试理路性质测试模型Property testing model · Property testing明确 oracle、距离和承诺间隔，用测试算法与下界区分局部违规、全局距离、容忍性和查询成本。通过距离承诺，系统研究哪些精确判定问题能够转化为前一种可抽样的任务。

继续建立下界时，可以把决策树与 证书复杂度理路证书复杂度Certificate complexity of Boolean functions · Boolean certificate complexity用足以强制某个固定输入函数值的最少已知坐标数，分别度量 0-证书与 1-证书。等结构量联系起来；使用任何此类关系前，先确认讨论的是全函数还是承诺问题，以及成本是硬上限还是期望值。