容忍性质测试

普通 tester 可以把任何真实 violation 当作拒绝证据，因为 yes 输入完全干净；容忍测试面对的 close 输入本来就可能遍布少量违规。它必须判断的是错误总量是否越过第二道阈值，而不是有没有看见一处错误。

两阈值之间的宽度决定所需分辨率。Gap 大时，粗糙估计已足够把两侧分开；gap 缩小时，采样波动必须压得更低，查询量随之上升。许多 tolerant tester 因而更接近距离估计器，而不是传统的局部 witness 搜索器。

常量字符串的容忍测试 ​

令 $x\in \{0,1{\}}^n$，性质 $\mathcal{P}=\{0^n,1^n\}$。若 1 的比例为 $p$，则

均匀独立查询 $m$ 个坐标，令样本均值为 $\hat{p}$，并估计

函数 $u\mapsto min\{u,1-u\}$ 是 1-Lipschitz，所以 $|\hat{d}-d|\le |\hat{p}-p|$。Hoeffding 界说明

足以把估计误差控制在 $\mathrm{\Delta }/3$。取阈值 $({\epsilon }_1+{\epsilon }_2)/2$：close 对象高概率落在阈值下，far 对象高概率落在阈值上。

与非容忍常量测试相比，这里不能见到一对不同 bit 就立即拒绝；close 对象本来允许含少量少数 bit。Tester 必须估计少数比例，而不是只寻找一个局部 violation。

容忍性为何可能更难 ​

普通 tester 的 yes 输入完全满足性质，常能依靠 perfect completeness 和局部 witness；tolerant tester 必须接受整个 ${\epsilon }_1$ 邻域，其中已经存在许多 witness。拒绝规则要判断违规的 总量 是否越过远阈值。

对某些性质，普通测试只需常数或 poly$(1/\epsilon )$ 查询，tolerant testing 却接近学习或距离估计的复杂度。不能从基础 tester 通过“把拒绝次数阈值调高”无条件得到正确算法；需要违规计数与全局距离之间的稳定关系。

错误侧别与适应性 ​

Tolerant 与 one-sided/two-sided 是不同轴。当 ${\epsilon }_1>0$ 时，close 但不满足性质的对象也必须高概率接受；一个发现真实局部 violation 就必拒绝的 perfect-completeness 规则通常不再适用。

查询仍可自适应或非自适应。上面的样本均值 tester 非自适应；某些距离估计算法会根据粗估结果把后续查询集中到可疑区域。容忍性本身不规定访问顺序。

边界 ​

距离必须与对象表示一致。对图性质，dense 与 bounded-degree 距离给同一图不同 close/far 身份；阈值不能脱离 oracle 单独搬用。

如果 ${\epsilon }_1={\epsilon }_2$，promise 没有间隔，采样噪声下通常不能以有限次查询统一分辨边界两侧；定义要求严格 ${\epsilon }_1<{\epsilon }_2$。

最后，接受 close 对象不等于输出修复后的成员，也不保证找到最近对象。Tolerant testing 仍只输出一个 gap decision bit；local reconstruction 是额外任务。

能把 $d(x,\mathcal{P})$ 估到小于 gap 的加性误差，就能在阈值中点得到 tolerant tester；反过来，对多组阈值带置信度地调用 tester，可以形成粗距离估计。这种联系解释了容忍测试为何常比 exact-versus-far 测试昂贵，也要求把每次调用的失败概率纳入总预算。

应用到图、分布或编码性质时，${\epsilon }_1,{\epsilon }_2$ 必须与同一表示、距离和 oracle 绑定。Close 邻域的语义一旦改变，算法需要估计的“错误总量”也随之改变，不能只复制一个 ${\mathrm{\Delta }}^{-2}$ 采样式。