查询复杂度的对偶多项式见证

有符号见证消去全部低次多项式方向，却与目标函数保持可见相关性 — 近似次数的对偶多项式见证

形式陈述

设 $f:D\to\{0,1\}$ ， $\varnothing\ne D\subseteq\{0,1\}^n$ ，取整数 $d\ge0$ 与 $0\le\varepsilon<1/2$ 。本页采用承诺域外不加限制的近似次数。令 $V_d$ 是所有次数至多 $d$ 的实多项式限制到 $D$ 后形成的有限维线性空间。近似次数满足

\widetilde{\deg}_\varepsilon(f)>d

当且仅当存在函数 $\psi:D\to\mathbb R$ ，使

\sum_{x\in D}|\psi(x)|=1,

并且对每个 $p\in V_d$ 都有

\sum_{x\in D}\psi(x)p(x)=0,

同时

\sum_{x\in D}\psi(x)f(x)>\varepsilon.

可把 $\psi$ 整体乘 $-1$ ，所以最后一个相关性不等式无需绝对值。第二个条件称 pure high degree 大于 $d$ ；在 $\{-1,+1\}$ 编码中，只需检查所有 $|S|\le d$ 的 Fourier character

\chi_S(z)=\prod_{i\in S}z_i.

有限维线性规划强对偶给出该刻画。具体令 $A$ 的列为次数至多 $d$ 的多线性单项式在 $D$ 上的取值， $a$ 为系数向量。最佳误差是线性规划

\delta_d=\min_{a,\ t\ge0}\{t:-t\mathbf1\le Aa-f\le t\mathbf1\}.

其对偶为

\max_{\psi}\{\langle\psi,f\rangle:A^{\mathsf T}\psi=0,\ \|\psi\|_1\le1\}.

Primal 可行且下界为零，故两侧最优值相等并可达到。若 $\delta_d>\varepsilon\ge0$ ，最优见证非零；若其一范数小于一，归一化会进一步增加正相关性，所以存在一范数等于一的所需见证。这证明必要性。

反过来，若三个见证条件成立，并假设某个 $p\in V_d$ 满足 $\|f-p\|_\infty\le\varepsilon$ ，则

\sum_x\psi(x)f(x) =\sum_x\psi(x)(f(x)-p(x)) \le\sum_x|\psi(x)|\,\|f-p\|_\infty \le\varepsilon,

与严格相关性矛盾。这证明充分性，因而见证是完备的排除条件。

直觉

Primal 试图让低次多项式同时穿过所有误差带；dual 则给输入点加正负质量，把每个低次方向完全抵消，却让目标函数仍留下可见偏置。一个短向量 $\psi$ 因而能替代“枚举所有低次多项式”的不可能任务。

一范数归一不是装饰。若没有它，可把任意非零相关性无限放大；若只要求均值为零，则仅消除了常数项，线性、二次等低次方向仍可能解释目标。Pure high degree 必须逐层消去全部 $V_d$ 。

例子与边界

对 $\operatorname{OR}_2$ ，按 $00,01,10,11$ 顺序定义

\psi=\left(-\frac12,\frac14,\frac14,0\right).

它的一范数为 $1$ ，总和为 $0$ ，所以与全部次数 $0$ 的常数多项式正交。OR 的值为 $(0,1,1,1)$ ，相关性为

\langle\psi,\operatorname{OR}_2\rangle =\frac14+\frac14 =\frac12>\frac13.

因此 $\widetilde{\deg}_{1/3}(\operatorname{OR}_2)>0$ 。另一方面线性多项式 $p=(2/3)(x_1+x_2)$ 在四点上的值为 $0,2/3,2/3,4/3$ ，最大误差为 $1/3$ ；两边合起来得到近似次数恰为 $1$ 。见证的每个约束和上界多项式都可直接复算。

Promise 域是见证的一部分。若把域限制为所有非零输入，OR 恒为 $1$ ，常数多项式已经精确计算它；上面的 $\psi$ 在非法点 $00$ 放了负质量，不能继续作为该 promise 的 dual。把 total-function 见证机械截断到合法域通常也会破坏正交。

编码也需一致。 $0/1$ 与 $\pm1$ 通过仿射替换保持次数，但相关性阈值和目标函数会相应变换；不能保留 $\psi$ 数值却只替换公式一侧的编码。

推论与应用

对偶见证把 approximate-degree 下界变成可组合对象：可以对已有 $\psi$ 做张量、块组合或质量重分配，同时单独验证一范数、pure high degree 与相关性。查询算法到接受多项式的转换再把证书翻译为查询下界：经典随机算法有 $\deg p\le T$ ，量子算法有 $\deg p\le2T$ ，所以这样的见证分别迫使 $T>d$ 与 $2T>d$ 。

见证只证明没有低次一致逼近，不证明查询算法上界，也不控制多项式系数大小。若错误是 one-sided、平均 $L_2$ 或 sign approximation，primal 约束改变，dual 条件也必须重新推导。

参考资料

Mark Bun and Justin Thaler, Approximate Degree in Classical and Quantum Computing，§6 的最优误差 primal/dual；本页使用 $0/1$ 输出、次数至多 $d$ 与有限承诺域的对应版本。
Mark Bun and Justin Thaler, “Dual Lower Bounds for Approximate Degree and Markov–Bernstein Inequalities,” Information and Computation 243, 2015, pp. 2–25.
Alexander A. Sherstov, “Communication Lower Bounds Using Dual Polynomials,” Bulletin of the EATCS 95, 2008, pp. 59–93.
Alexander A. Sherstov, “The Pattern Matrix Method,” SIAM Journal on Computing 40(6), 2011, pp. 1969–2000.

形式陈述 ​

反向链接

形式陈述