性质测试模型 | Codeboy's Blog

形式陈述

性质、距离与访问接口

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

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

d_n(x,\mathcal P_n) =\inf_{y\in\mathcal P_n}d_n(x,y).

若 $d_n(x,\mathcal P_n)\ge\varepsilon$ ，称 $x$ 是 $\varepsilon$ -far：把它改成任何满足性质的对象都至少要付出 $\varepsilon$ 比例的基本编辑。到性质的距离会区分字符串、编辑和图表示下的分母；只写“差很多”不能确定测试问题。

性质测试的实例由 $(n,\varepsilon)$ 、性质、距离和 oracle 共同决定。查询复杂度 $q(n,\varepsilon)$ 统计访问对象的次数，本地计算通常像查询复杂度模型一样免费。若单次答案长度、生成查询的时间或存储状态也重要，应作为额外资源分别报告。

完备性与可靠性量词

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

\begin{aligned} x\in\mathcal P_n &\Longrightarrow \Pr_R[T^x(n,\varepsilon;R)=\mathrm{accept}]\ge\frac23,\\ d_n(x,\mathcal P_n)\ge\varepsilon &\Longrightarrow \Pr_R[T^x(n,\varepsilon;R)=\mathrm{reject}]\ge\frac23. \end{aligned}

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

最关键的第三种情形是

0<d_n(x,\mathcal P_n)<\varepsilon.

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

距离为零的对象应接受，距离至少 epsilon 的对象应拒绝，中间 gap 不作承诺 — 性质测试的 exact-versus-far gap

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

直觉

性质测试不试图看清整个对象，而是利用“远离”把全局错误放大成可抽样的密度或结构。若修复对象必须改动常数比例的基本单元，一个设计得当的 tester 就可能只看少量局部视图，仍以常数概率撞见无法与任何合法对象兼容的迹象。

Gap 是这种节省的关键。测试器必须确认精确属于性质，也必须排除已经远离的对象，却可以不裁决中间薄层；它用放弃边界附近的精确分类，换取远少于完整输入规模的访问。对具体性质而言，真正的证明工作是把“需要许多编辑”转成“查询分布容易看见的证据”。

例子与边界

全零字符串测试器

令 $\Omega_n=\{0,1\}^n$ ，性质 $\mathcal P_n=\{0^n\}$ ，距离取归一化Hamming 距离。测试器独立均匀抽取 $q$ 个坐标并查询；只要看见一个 $1$ 就拒绝，所有回答均为 $0$ 才接受。

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

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

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

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

gap 内的真实失败边界

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

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

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

模型边界

局部随机访问并不足以唯一确定一个模型。性质测试通常查询待测对象本身；概率可检验证明查询额外提供的证明，统计查询得到的则是分布下期望值的近似。可选择坐标、IID 抽样和条件采样也有不同的信息能力，因此查询上界只有在对象表示、距离和 oracle 均一致时才能比较。

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

推论与应用

评价一条性质测试结论时，应把对象表示、距离分母、oracle、错误侧、适应性和查询口径作为同一个规格读取。查询数相同而其中任一项不同，可能代表完全不同的信息能力；尤其不能把 sample access、坐标访问和块查询混成“都只问了一次”。

这套模型为图测试、分布测试、函数性质与局部可测试码提供共同语言。共同之处是 exact-versus-far 的量词，差异则落在每个领域如何定义基本编辑和局部视图；可复用的是证明框架，不是未经重证的具体采样率。

变体应从规格出口继续阅读：容忍性质测试区分“足够近”与“足够远”，distance estimation 试图估计实际距离，distribution-free testing 则让距离参考未知输入分布。它们改变的是 promise、访问能力或输出目标，不应作为普通 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.

形式陈述 ​

性质、距离与访问接口 ​

完备性与可靠性量词 ​

全零字符串测试器 ​

gap 内的真实失败边界 ​