近似次数

精确表示要穿过每一个目标点；一致逼近允许在每个目标值周围留出一条误差带。多项式可以重新平衡所有点的偏差，从而降低次数，但不能把少数困难输入藏进平均值。

放宽误差会扩大可选多项式集合，所以 ${\epsilon }_1\le {\epsilon }_2$ 时有

阈值 $1/2$ 则有本质意义：一旦允许 $\epsilon \ge 1/2$，常数 $p\equiv 1/2$ 就能逼近任何 $0/1$ 函数。把误差限制在它以下，才保留了两种答案之间的间隙。

四个输入就能看见“降次” ​

${\mathrm{OR}}_2$ 的精确表示为 $x_1+x_2-x_1{x}_2$，次数是 $2$。改用

后，逐点检查如下：

因此一次多项式已经够用。常数 $c$ 却必须同时满足 $|c|\le 1/3$ 和 $|c-1|\le 1/3$，两个可行区间不相交，故

其中 $p(1,1)=4/3$ 完全合法，却不能直接充当一个算法的接受概率。若逐点把它截断成 $min(1,max(0,p))$，取值虽回到概率范围，多项式次数却可能上升，因为截断是分段操作。此例截断后恰回到 $0,2/3,2/3,1$ 四个值，它们的唯一多线性表示为 $\frac{2}{3}{x}_1+\frac{2}{3}{x}_2-\frac{1}{3}{x}_1{x}_2$，次数已升到 $2$。

OR 可以大幅降次，奇偶函数不能 ​

对 $n$ 个变量，经典结果给出

而其精确次数为 $n$。

相反，奇偶函数在任意固定误差 $\epsilon <1/2$ 下仍需要次数 $n$。一个简洁证明是在 $\{-1,1{\}}^n$ 上考察符号编码 $F(z)=\prod _{i=1}^n{z}_i$。若存在次数小于 $n$ 的 $q$，使 $|F-q|\le \eta <1$，对均匀随机的 $z$ 取期望：$q$ 的每个单项式都漏掉至少一个变量，该变量在 $Fq$ 中出现奇数次，于是 $\mathbb{E}[Fq]=0$。但同时

矛盾。输出从 $0/1$ 改成 $\pm 1$ 会把误差变为 $2\epsilon$；输入的仿射替换不改变次数，所以这个证明也适用于原编码。

承诺外是否有界，会改变答案 ​

假设 OR 的合法输入只含零个或一个 $1$。本页口径下，$p(x)=\sum _i{x}_i$ 在全部合法输入上精确正确，次数仅为 $1$；它在承诺外可能大于 $1$，但不违反定义。

另一种偏函数近似次数还要求多项式在整个布尔立方体上有界，例如落在 $[-\epsilon ,1+\epsilon ]$。在这种口径下，上述线性多项式不再合格，同一个承诺 OR 在常数误差下需要 $\mathrm{\Omega }(\sqrt{n})$ 次数。引用偏函数结果时，必须先核对这个额外条件；它不是无关紧要的记号差别。

几种邻近概念 ​

符号表示只要求多项式在两类输入上有正确的正负号，幅值可以任意；一致逼近还要求它接近指定数值。分布 $L_2$ 逼近控制 $\mathbb{E}[(p-f{)}^2]$，允许低概率输入承担较大误差。单侧近似则对两种输出施加不同约束，其具体定义需要单独写出。这些参数解决的问题不同，不能相互代称。

近似次数成为查询下界，依靠的是一条额外的“算法到多项式”桥梁：最多查询 $T$ 次的随机决策树，其接受概率可写成次数至多 $T$ 的多项式；最多查询 $T$ 次的量子查询算法，其接受概率次数至多 $2T$。因此，对逐输入错误至多 $\epsilon$ 的相应算法，

这两个 $T$ 都是最坏查询次数，不能直接替换成期望次数。对偏函数，算法的接受概率在承诺外仍然有界，所以本页不限制承诺外的定义可能给出较弱下界，正如前面的承诺 OR。

逆向转换不自动成立：低次多项式可能超出概率范围，也可能需要难以实现的系数结构。上界需要构造并逐点验证一个多项式；下界则要排除所有低次多项式。后者可以用对称化、正交性或对偶多项式见证理路查询复杂度的对偶多项式见证Dual polynomial witness for query complexity · Approximate-degree dual witness用一范数归一、与全部低次多项式正交的有符号见证，认证不存在给定误差的低次逼近。完成，不能仅说明某个自然候选失败。