查询复杂度模型

输入坐标 oracle ​

设输入 $x=(x_1,\dots ,x_n)\in {\mathrm{\Sigma }}^n$ 不直接交给算法，而由 oracle 保存。一次标准坐标查询选择索引 $i\in [n]$，oracle 返回符号 $x_i$，并计一个单位成本。算法可以免费计算已经看到的答案、维护任意内部状态，再决定下一次询问哪个坐标。

对布尔函数公理库布尔函数Boolean function以有限 Boolean cube 为定义域、输出单个真假值的函数，并区分偏函数、支持变量与限制操作。 $f:S\to \{0,1\}$，其中 $S\subseteq \{0,1{\}}^n$ 是 total 或 promise 定义域，算法的目标是在所有合法输入上输出 $f(x)$。输入长度 $n$ 和查询次数 $q$ 是不同参数：算法即使只问 $q\ll n$ 个位置，也知道 $n$、promise $S$ 和函数规格，却不能从未询问坐标中免费读取信息。

查询之外的计算不计费，这使模型专注于访问瓶颈。一个查询上界可能使用昂贵计算来挑选下一个坐标，不一定对应快速 RAM 程序；反过来，在免费计算下仍证明需要许多查询，便得到不依赖具体实现技巧的信息下界。

执行 transcript 与决策树 ​

确定性算法在第 $t$ 步选择

$$i_t={\varphi }_t((i_1,x_{i_1}),\dots ,(i_{t-1},x_{i_{t-1}})).$$

因此后一次索引可以依赖先前答案，这叫自适应查询。完整问答序列是执行 transcript；当算法停止时，所有与该 transcript 一致的合法输入必须具有同一 $f$ 值，否则叶上的单一输出不可能同时正确。

这正是决策树模型公理库决策树模型Decision-tree model · Comparison decision tree用查询节点、答案分支和输出叶刻画算法能够区分输入所需的信息深度。在坐标查询集合上的特化。内部结点标记索引 $i$，从结点离开的边标记可能答案 $a\in \mathrm{\Sigma }$，叶标记输出。对二进制输入是二叉树；若字母表有 $k$ 个符号，则一个查询结点最多有 $k$ 个答案分支，但仍只计一次查询。

根叶路径长度是该输入上的查询数，最大深度是最坏查询成本。树的大小可能指数巨大，却不计入查询复杂度；这再次表明模型不衡量描述长度或本地时间。

OR 的逐步执行 ​

对

$${\mathrm{OR}}_n(x)=x_1\vee \cdots \vee x_n,$$

一个确定性算法依次查询坐标，看到第一个 $1$ 就输出 $1$，若全部查询后仍未看到 $1$ 才输出 $0$。在输入 $00100$ 上，按从左到右的顺序得到 transcript

$$(1,0),(2,0),(3,1).$$

三次查询后即可停止。对 $0^n$，算法必须读完全部 $n$ 位才能确认没有遗漏的 $1$，这条路径长度为 $n$。

“必须读完”可以用一致输入证明。若算法在 $0^n$ 上有某个坐标 $j$ 未查询，把该位改为 $1$ 得到 $e_j$；两份输入对已问坐标给出完全相同的答案，但 OR 值分别为 $0$ 与 $1$。算法会走到同一叶并输出同一值，至少错一份。因此任意确定性坐标查询算法在某个输入上需要 $n$ 次查询。

这个例子区分实例成本和最坏成本。某些输入很早暴露一个见证，不意味着函数的最坏查询复杂度很小；下界专门构造没有早期见证、且每个未看坐标仍可能改变答案的路径。

查询集合是模型的一部分 ​

若一次允许问“是否存在值为 $1$ 的坐标”，OR 一次查询即可解决；若允许返回区间和，也可用不同策略定位非零位。这些不是更聪明的同一个坐标查询算法，而是更强的 oracle。任何查询界都必须同时声明可问问题、每次答案包含多少信息以及成本单位。

预言机图灵机公理库预言机图灵机Oracle Turing machine可在一步内查询某固定语言成员资格的相对可计算性模型。询问某个构造出的字符串是否属于固定语言，研究相对可计算性；本页 oracle 只读取当前输入的一个坐标。统计查询公理库统计查询模型statistical query model · SQ model让学习器查询有界统计量的近似期望，并以查询数、容差和计算量衡量效率。返回有界统计量的近似期望，成员/等价查询则询问目标概念标签或提交完整候选。它们都使用“query”一词，却暴露不同信息，复杂度不能横向换算而不先给归约。

数据库查询也可能返回整张关系表，单次答案长度随数据增长；把它算成一次坐标查询会隐藏输出成本。单元探测模型公理库单元探测模型Cell-probe model将内部计算设为免费、只统计对 w 位内存单元读写次数的数据结构复杂度模型。更接近内存访问，但每次读取 $w$ bit cell，并允许预处理后的存储布局；标准 bit-query 模型直接面对原输入坐标，两者的空间与字宽参数不同。

随机性、promise 与失败边界 ​

随机查询算法可以先用随机币选择一棵确定性决策树，或在执行中随机选下一坐标。复杂度必须声明零误差还是 bounded error，以及查询数对随机币取硬上限还是期望。完整定义由确定性与随机查询复杂度公理库确定性与随机查询复杂度Deterministic query complexity · Randomized query complexity在坐标访问模型中分别定义确定性、零误差随机和有界误差随机查询复杂度，并固定最坏与期望口径。分别整理。

promise 也会改变“一致输入”集合。下界中的替代输入必须仍在合法域 $S$；在 OR 的 total function 证明里，$0^n$ 与 $e_j$ 都合法。若 promise 排除 $e_j$，同一个未查询坐标论证可能立即失效。不能先在全 cube 上改输入，再忽略它已经越出问题定义域。

算法知道一个坐标值，不表示知道产生它的物理读取成本。远程存储、压缩文件和噪声 oracle 会为访问加入延迟、解码或错误参数；标准模型把它们抽掉。使用查询上界指导工程实现时，应把这些成本重新放回，而不是声称本地计算免费就意味着访问也免费。

参考资料

• Harry Buhrman and Ronald de Wolf, “Complexity Measures and Decision Tree Complexity: A Survey,” Theoretical Computer Science 288(1), 2002, pp. 21–43.
• Stasys Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012, Chapter 14.
• Noam Nisan, “CREW PRAMs and Decision Trees,” SIAM Journal on Computing 20(6), 1991, pp. 999–1007.