单调性测试

形式陈述 ​

偏序域上的性质 ​

设 $(P,⪯)$ 是有限非空偏序集，值域 $(R,\le )$ 是非空全序集。函数 $f:P\to R$ 是单调映射理路偏序集上的单调映射Monotone map on posets · Order-preserving map · Isotone map在偏序之间保持次序的映射，以及它作为单调算子参与不动点迭代时的基本结构。，当且仅当

对所有可比点成立。测试器理路性质测试模型Property testing model · Property testing明确 oracle、距离和承诺间隔，用测试算法与下界区分局部违规、全局距离、容忍性和查询成本。通过 value oracle 查询 $f(x)$，本地知道偏序关系和域大小。

距离通常按需要修改的函数表位置比例定义：

测试器要接受所有单调函数，拒绝距离至少 $\epsilon$ 的函数。它不负责输出最近单调修复，也不按违反关系对的比例直接定义 far。

Boolean cube ​

取整数 $n\ge 1$，最常见的域是 $P=\{0,1{\}}^n$，采用逐坐标偏序：$x⪯y$ 当且仅当每个 $i$ 都有 $x_i\le y_i$。对 Boolean-valued $f$，单调性禁止从较低点的 $1$ 走到较高点的 $0$。

Hasse 图的有向边连接只差一个从 $0$ 变 $1$ 的坐标。若某条边 $(x,x\oplus e_i)$ 满足

它是一个局部 violation，足以单侧拒绝。若所有 Hasse 边都不违反，则沿任意上升路径反复应用局部不减，函数对全部可比点单调。

Edge tester ​

一次 edge test 均匀选择 cube 中一条有向边，查询两端并在出现 $1\to 0$ 时拒绝。单调函数从不被拒绝，查询数为 $2$。

令 $V_i(h)$ 表示函数 $h$ 在第 $i$ 个方向上的违反边数，$V(h)=\sum _i{V}_i(h)$。下面通过逐坐标排序给出 soundness，不能只把局部违反边的端点覆盖当成全局修复。

定义 $S_i$：在每条第 $i$ 方向边上，把两端值按低点在前排序，即将 $(1,0)$ 交换成 $(0,1)$，其余不变。排序后第 $i$ 方向没有违反；对其他方向 $j$，违反数也不会增加。后一事实只需检查由 $i,j$ 张成的二维小面：对 $a,b,c,d\in \{0,1\}$，有

这正是排序两行之后，横跨两行的下降边数不增加；逐个检查十六种四元组即可验证。对全部小面求和，得到 $V_j(S_{i}h)\le V_j(h)$。

从 $h_0=f$ 开始依次取 $h_i=S_i{h}_{i-1}$。已排好的方向不会再次出现违反，故 $h_n$ 单调。第 $i$ 步只在 $V_i(h_{i-1})$ 条互不相交边上各改两个值，因此

若 $f$ 到单调性的距离至少 $0<\epsilon \le 1$，就有 $V(f)\ge \epsilon 2^{n-1}$。Cube 共有 $n{2}^{n-1}$ 条有向边，故一次随机边检验的拒绝概率至少为 $\epsilon /n$。[1]

独立重复 $q\ge \lceil n\ln 3/\epsilon \rceil$ 次，全部漏检概率至多 $e^{-q\epsilon /n}\le 1/3$，总查询至多 $2q$。这给出 $O(n/\epsilon )$ 上界；更精细算法还会使用长路径或更全局的比较，本页不声称该边测试器最优。

Violation graph 与距离 ​

定义无向简单 violation graph：顶点为 $P$，若 $x⪯y$ 但 $f(x)>f(y)$，就在两点间连边。任何修改集必须击中每条 violation，否则未修改的两个端点仍违反；因此修改集是该图的顶点覆盖理路顶点覆盖Vertex cover与图中每条边至少一个端点相交、从而覆盖全部边的顶点子集。。

对 Boolean-valued 函数，删除一个顶点覆盖 $C$ 后，剩余标记间不存在可比的 $1\to 0$。具体定义 $g(z)=1$ 当且仅当存在 $u\notin C$ 满足 $u⪯z$ 且 $f(u)=1$。这个 $g$ 单调；它保留每个未删除的 $1$，也不会把未删除的 $0$ 改为 $1$，否则原来就有一条未被覆盖的违反边。因此只需改动 $C$ 内的值。与修改集必为覆盖的方向合起来，最小顶点覆盖大小恰等于最少修改位置数。这个结构把“far”转换为许多互不相容的违反对，常用于 tester 分析。

只用 Hasse 边建立的图可能丢掉远距离可比对；虽然无局部违反等价于单调，但最小 cover 与完整 violation graph 的参数不必逐项相同。下界或精确距离论证要声明使用哪一张图。 例如三维 cube 上令 $f(x)=1$ 当且仅当 $|x|\le 1$。三个重量为一的点覆盖了全部局部违反边；但完整图中有四条顶点互不相交的违反对 $000\to 111$、$001\to 011$、$010\to 110$、$100\to 101$，每条都必须修改一个端点。故最少要改四个值，改成常零函数即可达到，距离恰为 $1/2$。局部覆盖的三个点并不足以完成单调修复。