查询复杂度模型

查询模型把输入藏在一排带编号的格子后面，只为掀开格子付费。算法可以对已经看到的内容做任意复杂推理，却不能从未访问的位置获得哪怕一 bit；因此下界通常构造两份在所有已问坐标上一致、函数值却不同的合法输入。

自适应决策树则记录“答案如何改变下一问”。一条短路径只证明某个输入很快暴露了证据，最坏复杂度要看最难叶；树的结点数和选择查询所需的计算都被模型抽掉，只剩访问深度这一条资源轴。

OR 的逐步执行 ​

对

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

三次查询后即可停止。对 $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”一词，却暴露不同信息，复杂度不能横向换算而不先给归约。

随机性、promise 与失败边界 ​

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

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

决策树把查询下界转成不可区分性问题：只要某条 transcript 仍容纳函数值不同的两个合法输入，算法就不能在该叶停止。Adversary、certificate、sensitivity 与 polynomial method 等技术，都是以不同方式证明低深度树无法把这些输入全部分开。

查询结果迁移到数据结构、远程访问或测试算法时，必须保留 oracle 的问题集合、答案格式与带宽。数据库查询可能返回整张关系，单元探测模型公理库单元探测模型Cell-probe model将内部计算设为免费、只统计对 w 位内存单元读写次数的数据结构复杂度模型。每次读取一个 $w$ bit cell，远程或噪声 oracle 还会引入延迟与错误；这些成本都不能被“记作一次 query”而消失。模型的抽象价值在于隔离访问瓶颈，而不是让不同访问操作可直接横向换算。