近似次数

一致逼近定义 ​

设 $f:\{0,1{\}}^n\to \{0,1\}$，$0\le \epsilon <1/2$。若实多项式 $p$ 满足

$$\underset{x\in \{0,1{\}}^n}{max}|p(x)-f(x)|\le \epsilon ,$$

就称 $p$ 在一致或 pointwise 意义下 $\epsilon$-逼近 $f$。$f$ 的近似次数定义为

$${\widetilde{\mathrm{deg}}}_{\epsilon }(f)=min\{\mathrm{deg}p:\Vert p-f{\Vert }_{\mathrm{\infty }}\le \epsilon \}.$$

最大值是有限 cube 上上确界公理库上确界与下确界Supremum and infimum在偏序中分别作为集合最小上界与最大下界的最紧边界元素。范数的具体形式。保证逐点成立，每个合法输入的误差都受限；在某个输入分布下均方误差很小，不足以证明一致逼近。

对偏函数 $f:S\to \{0,1\}$，最大值只在 $x\in S$ 上取，多项式在 promise 外可以任意。删去大量难点可能显著降低次数，所以 total 与 partial 结果必须分开。

与 exact degree 的关系 ​

当 $\epsilon =0$ 时，定义退化为精确表示，因此

$${\widetilde{\mathrm{deg}}}_0(f)=\mathrm{deg}(f).$$

若 $0\le {\epsilon }_1\le {\epsilon }_2$，每个 ${\epsilon }_1$-逼近多项式也是 ${\epsilon }_2$-逼近，所以

$${\widetilde{\mathrm{deg}}}_{{\epsilon }_2}(f)\le {\widetilde{\mathrm{deg}}}_{{\epsilon }_1}(f).$$

误差预算放宽只会扩大可选多项式集合。$\epsilon <1/2$ 保留输出 $0$ 与 $1$ 的可分 gap；若允许 $\epsilon \ge 1/2$，常数多项式 $p\equiv 1/2$ 已能逼近每个 Boolean function，度量失去区分力。

OR_2 的线性近似 ​

精确表示

$${\mathrm{OR}}_2(x_1,x_2)=x_1+x_2-x_1{x}_2$$

含非零二次项，所以 exact degree 为 $2$。考虑线性多项式

$$p(x_1,x_2)=\frac{2}{3}(x_1+x_2).$$

在四个输入上，$p$ 的值依次为 $0,2/3,2/3,4/3$，而 OR 值为 $0,1,1,1$；最大绝对误差恰为 $1/3$。因此

$${\widetilde{\mathrm{deg}}}_{1/3}({\mathrm{OR}}_2)\le 1.$$

次数 $0$ 的常数 $c$ 若同时在 00 与 10 上误差至多 $1/3$，需满足 $|c|\le 1/3$ 且 $|c-1|\le 1/3$，两个区间不交。因此次数不能为 $0$，最终

$${\widetilde{\mathrm{deg}}}_{1/3}({\mathrm{OR}}_2)=1.$$

这条四点检查展示近似次数为何可以严格小于 exact degree：多项式不再逐点等于 $0/1$，但每个偏差仍被同一阈值控制。它不是把二次项“忽略为小量”，而是重新选择了一条在全部输入上平衡误差的线性函数。

三种不能混用的近似 ​

一致双侧逼近要求 0-输入和 1-输入都落在各自目标值的 $\epsilon$ 邻域。One-sided approximation 会在一侧要求不越过阈值、另一侧允许不同误差形式，适合保留单侧拒绝或接受；其最低次数可能不同。

Sign degree 先把输出编码为 $\{-1,+1\}$，只要求多项式符号与函数一致，例如 $f(x)p(x)>0$，却不要求 $p(x)$ 靠近 $\pm 1$。把一个符号表示任意放大仍合法，所以它不提供 $\Vert p-f{\Vert }_{\mathrm{\infty }}$ 控制。

分布 $L_2$ 逼近只控制 ${\mathbb{E}}_{\mu }[(p(x)-f(x){)}^2]$。低质量输入可以有很大点误差；若要由它推出 uniform bound，需要额外结构，不能把 expectation 换成 max 而保持次数不变。

口径与应用边界 ​

系数大小在基本定义中不受限制。一个低次多项式可能需要极大系数或高精度表示；近似次数衡量代数次数，不自动给数值稳定或高效求值算法。

变量编码也重要。从 $0/1$ cube 换到 $\pm 1$ cube 有仿射代换，不改变总次数，但具体多项式和误差中心会改变。公式比较前应先统一编码。

低近似次数能否转成低查询算法、次数下界怎样推出查询下界，需要一条把算法接受概率多项式化的独立定理。本页只定义逼近对象并校准变体，不把这种后续方法当作定义自带的结论。

参考资料

• Noam Nisan and Mario Szegedy, “On the Degree of Boolean Functions as Real Polynomials,” Computational Complexity 4, 1994, pp. 301–313.
• Ronald de Wolf, “A Brief Introduction to Fourier Analysis on the Boolean Cube,” Theory of Computing Graduate Surveys 1, 2008, pp. 1–20.
• Alexander A. Sherstov, “The Pattern Matrix Method,” SIAM Journal on Computing 40(6), 2011, pp. 1969–2000, approximate-degree preliminaries.