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

固定随机币后，非自适应测试器面对所有可能答案仍走同一组查询地址；自适应测试器则让答案选择查询树的下一条分支。区别在“新地址是否由已见答案生成”，不在代码是否写成循环、查询是否串行发送，或发现 witness 后是否提前停止。

非自适应的常量串 tester ​

取 $n\ge 1$、$0<\epsilon \le 1/2$，要测试 $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。这里 $q$ 数的是坐标对，原始查询预算至多为 $2q$；重复坐标可缓存，也可在预算超过 $n$ 时直接读完整串。

真正自适应的邻接探索 ​

在 bounded-degree 图 oracle 中，查询 $(v,j)$ 返回顶点 $v$ 的第 $j$ 个邻居 $u$。若返回的 $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$ 个位置计。比较两种测试器时，要区分省略已经无用的查询与根据答案选择新地址。

错误与距离是独立坐标 ​

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

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

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