自适应与非自适应性质测试

固定随机币后的判据 ​

测试器在输入对象 $x$ 上使用随机带 $R$。固定 $R=r$ 后，若全部查询地址

$$q_1(r),\dots ,q_t(r)$$

在看到任何 oracle 回答前就已确定，则 tester 是非自适应的。它可以一次提交全部查询，最后根据回答向量决定接受或拒绝。

若第 $j$ 个查询可以写成

$$q_j={\varphi }_j(r,a_1,\dots ,a_{j-1}),$$

其中 $a_i$ 是先前 oracle 回答，则 tester 是自适应的。固定随机性后，它对应一棵决策树公理库决策树模型Decision-tree model · Comparison decision tree用查询节点、答案分支和输出叶刻画算法能够区分输入所需的信息深度。：内部结点是查询，答案选择后继，叶标记测试结果。

分类必须在固定随机币后检查。随机选择一批查询仍可非自适应，因为地址只依赖 $r$；“算法有随机过程”不表示查询依赖答案。

非自适应的常量串 tester ​

要测试 $x\in \{0,1{\}}^n$ 是否为常量串，可以预先独立均匀抽取 $q$ 对坐标 $(I_j,J_j)$，一次查询所有涉及位置，并在任一对回答不同的时候拒绝。

固定随机带后，全部索引对已经确定，oracle 回答不会改变后续查询集合，所以这是非自适应 tester。若 $x$ 中较少出现的 bit 比例为 $\alpha$，一对坐标取值不同的概率为 $2\alpha (1-\alpha )$；当 $x$ 距常量性质至少 $\epsilon \le 1/2$ 时，$\alpha \ge \epsilon$，故该概率至少 $\epsilon$。

独立重复 $q\ge \lceil \ln 3/\epsilon \rceil$ 对后，全部漏检概率至多 $(1-\epsilon {)}^q\le 1/3$。性质成员从不会出现不等对，因而测试还具有 perfect completeness。

把查询写在一个 for 循环里逐个执行，不会让它变成自适应；数据依赖关系而不是程序的时间顺序决定分类。

真正自适应的邻接探索 ​

在 bounded-degree 图 oracle 中，查询 $(v,j)$ 返回顶点 $v$ 的第 $j$ 个邻居 $u$。若 tester 接着查询 $(u,1)$，第二个地址中的顶点名来自第一次回答，固定随机币后仍无法预先知道，因此这是一条真实自适应轨迹。

例如从随机顶点 $v$ 出发探索半径两层的局部邻域：先读取 $v$ 的邻居列表，再对实际发现的每个 $u$ 读取其邻居。查询树的不同分支会访问不同顶点集合；把所有可能顶点的邻居都预查一遍可以消除适应性，却可能把查询量从局部规模膨胀到 $n$。

这个执行图像本身不证明某项图性质可测试。完整 tester 还需指定拒绝 witness，并证明每个 far 图以足够概率让探索遇到它；适应性只描述访问策略，不提供 soundness。

轮适应性 ​

查询还可分成 $r$ 个 batch。同一 batch 内地址同时确定，下一 batch 可依赖此前批次的全部回答。$r=1$ 是非自适应，无限制 $r$ 回到完全自适应；round complexity 记录二者之间的层级。

“查询可以并行执行”不自动表示非自适应。当前分支上的多个已知地址可以并行，但若第二批地址依赖第一批结果，算法仍至少有两轮。反过来，非自适应查询即使实现上串行发送，语义上仍只有一批。

提前停止的伪差异 ​

一个预先选定 $q$ 个坐标的 tester 看到第一个 witness 后立即停止，表面上后续查询数依赖回答。若将未执行位置视为已经预定、只是在拒绝后省略无用访问，它的最坏查询集合仍可非自适应实现；这种 early stopping 不等于利用答案选择新的地址。

实例查询数可能因此降低，但最坏上限仍为 $q$。若论文比较 expected queries，提前停止有意义；若只比较 worst-case query bound，把它称为自适应优势会夸大模型差异。

错误与距离是独立坐标 ​

自适应 tester 可以单侧或双侧错误，非自适应 tester 也一样。答案依赖性不决定完备性是否为 $1$；错误侧别公理库单侧与双侧性质测试器One-sided property tester · Two-sided property tester按性质内对象是否永不被拒绝，区分 perfect completeness 的单侧测试与两边都允许小概率错误的双侧测试。必须单独声明。

距离与 oracle 表示同样独立。一个在 dense adjacency matrix 中非自适应采样边对的算法，换到 bounded-degree neighbor oracle 后不一定仍能提出相同查询；比较适应性前要先固定可访问对象。

适应性可能降低查询数，也可能没有帮助。证明 separation 需要同一性质、同一距离、同一错误和同一 oracle 下的两套上/下界；只展示一个自适应算法不能证明任何非自适应算法都更差。

参考资料

• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapters 2 and 10.
• Eric Blais, Joshua Brody, and Kevin Matulef, “Property Testing Lower Bounds via Communication Complexity,” Computational Complexity 21, 2012, pp. 311–358.
• Clément Canonne and Tom Gur, “An Adaptivity Hierarchy Theorem for Property Testing,” Computational Complexity 27, 2018, pp. 671–716.