单侧与双侧性质测试器

两种错误结构 ​

给定性质 ${\mathcal{P}}_n\subseteq {\mathrm{\Omega }}_n$、距离和参数 $\epsilon$，单侧 tester 采用 perfect completeness convention：

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

它只可能把 far 输入误收，不会误拒真正满足性质的对象。双侧 tester 则允许两边都出错：

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

概率对每个固定对象只取测试器内部随机性。两种定义都保留性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。的 gap：距离严格介于 $0$ 与 $\epsilon$ 的对象仍无输出约束。

单侧证据必须可验证 ​

单侧拒绝意味着测试器观察到的局部 transcript 与任何性质成员都不相容。若同一问答 transcript 还能由某个 $y\in {\mathcal{P}}_n$ 产生，测试器在 $y$ 上也会沿同一路径拒绝，破坏 perfect completeness。

因此单侧 tester 往往寻找有限局部 witness，例如一条被禁止的边、一个违反方程的三元组或一组冲突约束。存在局部 witness 还不够；soundness 必须证明每个 $\epsilon$-far 对象含有足够多、能被查询分布命中的 witness。

双侧 tester 可以依据统计偏差拒绝，而不必展示一个单次可确定验证的反例。代价是性质成员也可能因采样噪声落入错误尾部，所以完备性只达到高概率。

常量字符串的单侧测试 ​

令 ${\mathcal{P}}_n=\{0^n,1^n\}$，距离为归一化 Hamming。测试器先查询坐标 $1$ 得到参考 bit $b=x_1$，再独立均匀抽 $q$ 个坐标；若任何回答不等于 $b$ 就拒绝，否则接受。

性质成员所有坐标相同，测试器必然接受。若 $x$ 距两个常量串都至少 $\epsilon$，无论 $b$ 是 $0$ 还是 $1$，至少 $\epsilon n$ 个坐标与 $b$ 相反；全部 $q$ 次抽样漏掉反色坐标的概率至多

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

取 $q\ge \lceil \ln 3/\epsilon \rceil$，far 输入被接受的概率至多 $1/3$。总查询数为 $q+1$，拒绝 transcript 还明确指出两个取值不同的坐标，确实不可能来自常量串。

平衡字符串的双侧测试 ​

设 $n$ 为偶数，性质由所有 Hamming 重量恰为 $n/2$ 的串组成。均匀独立抽取 $q$ 个坐标，令样本均值为 $\hat{p}$；若

$$|\hat{p}-1/2|\le \epsilon /2$$

则接受，否则拒绝。性质成员的真实均值为 $1/2$，但有限样本仍可能偏出阈值，所以这不是单侧测试。

若输入到平衡性质的距离至少 $\epsilon$，其真实 1-比例 $p$ 满足 $|p-1/2|\ge \epsilon$。只要 $|\hat{p}-p|<\epsilon /2$，两类输入都会被正确处理。Hoeffding 界使失败概率至多 $2e^{-q{\epsilon }^2/2}$，取 $q=O({\epsilon }^{-2}\log \left(1/\delta \right))$ 可将双侧错误压到 $\delta$。

这个 tester 依据样本频率而非一个确定违规坐标作答。某个平衡串也可能抽到全 $0$ 样本并被拒绝，正是双侧错误允许、单侧错误禁止的事件。

放大规则 ​

对单侧 tester，独立重复并在任一副本拒绝时拒绝，仍保持 perfect completeness；far 输入所有副本都漏掉 witness 的概率乘法下降。若改用多数表决，虽然也可放大，却没有利用单侧结构。

双侧 tester 通常独立重复并多数表决。每次成功概率需与 $1/2$ 有固定间隔，且重复随机性足够独立；机械复用同一查询集合不会产生 Chernoff 型下降。查询数会按重复次数增长。

不相关的分类轴 ​

单侧/双侧只描述错误发生在哪一边，不描述查询是否自适应公理库自适应与非自适应性质测试Adaptive property testing · Nonadaptive property testing按后续查询地址能否依赖此前 oracle 回答，区分自适应测试、非自适应测试与分批轮次。。单侧算法可以根据早期回答选择后续查询，双侧算法也可以一次预先确定全部位置。

它也不等于 tolerant testing。基础单侧 tester 在 $x\in \mathcal{P}$ 时完美接受，对距离小但非零的对象没有承诺；“容忍少量错误”要求 positive close 阈值，是另一种 promise。

最后，单侧不意味着确定性。随机位置决定能否发现 witness，far 输入仍有漏检概率；perfect completeness 只固定性质成员这一侧的所有随机轨迹。

参考资料

• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapters 1–3.
• 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.
• Dana Ron, “Property Testing: A Learning Theory Perspective,” Foundations and Trends in Machine Learning 1(3), 2008, pp. 307–402.