容忍性质测试

普通单侧错误测试器若找到一个确实排除性质成员的局部见证，就可以拒绝；容忍测试面对的 close 输入本来就可能遍布少量违规。它必须判断的是错误总量是否越过第二道阈值，而不是有没有看见一处错误。

两阈值之间的宽度决定所需分辨率。间隔大时，粗糙估计已足够把两侧分开；间隔缩小时，采样波动必须压得更低，查询量随之上升。许多容忍测试器因而更接近距离估计器，需要汇总多个观察，而非找到一个局部见证就停止。

常量字符串的容忍测试 ​

令 $n\ge 1$、$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 界理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。说明

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

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

容忍性为何可能更难 ​

普通 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$，且某个输入距离恰为 $\epsilon$，该输入会同时要求接受概率至少 $2/3$ 与拒绝概率至少 $2/3$，规格直接矛盾。即使改成不重叠的严格端点，在有限坐标空间里读完输入仍能精确判定；失去正间隔主要会破坏统一的少量抽样保证。因此定义明确要求 ${\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}$ 采样式。