性质测试模型

性质、距离与访问接口 ​

对每个规模 $n$，先选择对象空间 ${\mathrm{\Omega }}_n$ 与性质子集 ${\mathcal{P}}_n\subseteq {\mathrm{\Omega }}_n$，再分别指定表示、距离和 oracle；三者是模型参数，不由“性质测试”四字预设为字符串、Hamming 距离或分布抽样。测试器不读取对象的完整表示，而通过规定的 oracle 提问：字符串模型可以查询坐标，稠密图模型可以查询一对顶点是否相邻，其他表示也有各自的合法问题和答案。

还需给出归一化距离 $d_n:{\mathrm{\Omega }}_n\times {\mathrm{\Omega }}_n\to [0,1]$。对象 $x$ 到性质的距离记为

$$d_n(x,{\mathcal{P}}_n)=\underset{y\in {\mathcal{P}}_n}{inf}{d}_n(x,y).$$

若 $d_n(x,{\mathcal{P}}_n)\ge \epsilon$，称 $x$ 是 $\epsilon$-far：把它改成任何满足性质的对象都至少要付出 $\epsilon$ 比例的基本编辑。到性质的距离公理库到性质的距离Distance to property · Distance from a property取对象到性质中最近合法对象的归一化距离，并据此精确定义 close、far 与测试 promise。会区分字符串、编辑和图表示下的分母；只写“差很多”不能确定测试问题。

性质测试的实例由 $(n,\epsilon )$、性质、距离和 oracle 共同决定。查询复杂度 $q(n,\epsilon )$ 统计访问对象的次数，本地计算通常像查询复杂度模型公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。一样免费。若单次答案长度、生成查询的时间或存储状态也重要，应作为额外资源分别报告。

完备性与可靠性量词 ​

一个双侧错误 $\epsilon$-tester $T$ 通常满足

$$\begin{array}{rl}x\in {\mathcal{P}}_n& ⟹{\text{Pr}}_R[T^x(n,\epsilon ;R)=\mathrm{accept}]\ge \frac{2}{3},\\ d_n(x,{\mathcal{P}}_n)\ge \epsilon & ⟹{\text{Pr}}_R[T^x(n,\epsilon ;R)=\mathrm{reject}]\ge \frac{2}{3}.\end{array}$$

对象 $x$ 先固定，概率只对测试器内部随机币 $R$ 取。这里的 $2/3$ 是可放大的常数约定，不是性质的一部分；若改成 $1-\delta$，查询量通常还会依赖 $\log \left(1/\delta \right)$。

最关键的第三种情形是

$$0<d_n(x,{\mathcal{P}}_n)<\epsilon .$$

定义对这层输入没有接受或拒绝要求。测试器处理的是一个 gap decision：确认精确属于性质，或发现对象已经远离；它不是对每个对象都近似计算距离，更不保证输出最近的合法对象。

若满足性质时总是接受，就具有 perfect completeness，也常称单侧错误；允许性质内对象也以小概率被拒绝，则是双侧错误。错误结构、自适应性和容忍 close/far 两个正阈值是不同坐标，不能用一个“随机测试器”标签全部代替。

全零字符串测试器 ​

令 ${\mathrm{\Omega }}_n=\{0,1{\}}^n$，性质 ${\mathcal{P}}_n=\{0^n\}$，距离取归一化Hamming 距离公理库Hamming 距离Hamming distance两个等长字在对应位置不同的坐标数。。测试器独立均匀抽取 $q$ 个坐标并查询；只要看见一个 $1$ 就拒绝，所有回答均为 $0$ 才接受。

当 $x=0^n$ 时，任何查询都返回 $0$，所以测试器必然接受。若 $x$ 是 $\epsilon$-far，则至少 $\epsilon n$ 个坐标为 $1$。一次查询漏掉全部错误位置的概率至多 $1-\epsilon$，$q$ 次独立抽样全部漏掉的概率至多

$$(1-\epsilon {)}^q\le e^{-\epsilon q}.$$

取 $q\ge \lceil \ln \left(1/\delta \right)/\epsilon \rceil$，远离输入被误收的概率至多 $\delta$。对目标常数错误 $1/3$，只需 $O(1/\epsilon )$ 次查询，与 $n$ 无关。这不是因为测试器重建了字符串，而是远离保证让违规坐标具有可抽中的密度。

看见第一个 $1$ 后即可立即拒绝；也可以预先选定全部 $q$ 个位置再统一查询。前者的实际查询数随回答变化，后者是非自适应的固定查询集合，但上述最坏查询界与可靠性估计对两种执行方式都成立。

gap 内的真实失败边界 ​

设 $x$ 只有一个 $1$，且 $1/n<\epsilon$。它不属于 ${\mathcal{P}}_n$，却也不 $\epsilon$-far。测试器若抽中那一位便拒绝，没抽中就接受；两种结果都符合定义。拿这个输入指责测试器“有时判断错误”，是把 exact membership 的规格错误地加到了 gap 模型上。

反过来，若论证声称远离输入会以常数概率暴露局部违规，就必须证明违规质量至少与 $\epsilon$ 成比例。一个全局性质可能只有稀少的直接违例，却仍需大量修改才能修复；从“far”到“许多可见局部证据”的桥梁不是定义自带的，需要针对性质证明。

归一化也不能省略。raw Hamming 距离为 $\epsilon$ 没有规模一致的意义；对长度 $n$ 字符串，通常以 $d_H/n$ 计比例。若 oracle 一次返回一个包含许多坐标的块，查询数还会被答案带宽改变，不能与 bit-query 结果直接比较。

模型边界 ​

局部随机访问并不足以唯一确定一个模型。性质测试通常查询待测对象本身；概率可检验证明公理库概率可检验证明Probabilistically checkable proof · PCP允许随机验证者把证明视为只读 oracle，并用受限随机位和局部查询区分正确与伪造证明的系统。查询额外提供的证明，统计查询公理库统计查询模型statistical query model · SQ model让学习器查询有界统计量的近似期望，并以查询数、容差和计算量衡量效率。得到的则是分布下期望值的近似。可选择坐标、IID 抽样和条件采样也有不同的信息能力，因此查询上界只有在对象表示、距离和 oracle 均一致时才能比较。

性质测试只承诺解决上述 gap decision，不自动给出修复方案、距离估计或完整违例证书。若任务要求区分“距离至多 ${\epsilon }_1$”与“距离至少 ${\epsilon }_2$”、估计实际距离，或局部重建一个近邻合法对象，就必须另行写出输入承诺、输出规格和查询资源；这些能力不能从 tester 的接受概率直接推出。

参考资料

• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapters 1–3.
• Ronitt Rubinfeld, “Taming Big Probability Distributions,” XRDS 19(1), 2012, pp. 24–28, and associated sublinear-algorithms surveys.
• Oded Goldreich, Shafi Goldwasser, and Dana Ron, “Property Testing and Its Connection to Learning and Approximation,” Journal of the ACM 45(4), 1998, pp. 653–750.