多项式逼近中的下界证明方法

### 多项式逼近中的下界证明方法 在计算复杂性理论中，确定函数的多项式逼近的下界是一个重要的研究方向。本文将介绍通过对称化和对偶多项式两种方法来证明函数多项式逼近下界的相关内容。 #### 1. 任意对称函数的下界证明 ##### 1.1 阈值度下界 对于对称布尔函数 \(f(x): \{ - 1,1\}^n \to \{ - 1,1\}\)，若 \(f(x) = F(|x|)\)，且 \(F(i - 1) \neq F(i)\) 对于 \(k\) 个 \(i \in [n]\) 成立。设 \(p\) 是符号表示 \(f\) 的多项式，\(q\) 是 \(p\) 的 Minsky - Papert 对称化多项式。由于 \(q\) 是单变量多项式，且 \(q(i - 1) \neq q(i)\) 对于 \(k\) 个 \(i \in [n]\) 成立，当 \(k > 0\) 时，\(q\) 是至少有 \(k\) 个根的非零多项式，所以 \(deg(q) \geq k\)。又因为 \(deg(q) \leq deg(p)\)，所以 \(p\) 的符号表示度至少为 \(k\)。 ##### 1.2 近似度下界 以对称的 \(t\) - 阈值函数 \(THR_t: \{ - 1,1\}^n \to \{ - 1,1\}\) 为例，当 \(|x| > t\) 时，\(THR_t(x) = - 1\)。Paturi 最初使用对称化和 Markov - Bernstein 不等式证明了 \(deg(THR_t) \geq \Omega(\sqrt{tn})\)。以下是其证明思路： 设 \(p\) 是 \(THR_t\) 的 \(d\) 度多项式逼近，\(q\) 是其 Minsky - Papert 对称化多项式，定义 \(Q(\xi) := q(n(\xi + 1)/2)\)。\(Q(\xi)\) 满足 \(|Q(\xi)| \leq 1\) 对于所有 \(\xi \in [-1,1]\) 且为 \(2/n\) 的整数倍。同时，\(Q( - 1 + 2(t - 1)/n) \in [2/3,4/3]\)，\(Q( - 1 + 2t/n) \in [-4/3, - 2/3]\)，所以存在 \(x^* \in [-1 + 2t/n - 2/n, - 1 + 2t/n]\) 使得 \(Q'(x^*) > n/2\)。 若 \(|Q(\xi)| \leq 1\) 对于所有 \(\xi \in [-1,1]\) 成立，根据 Markov - Bernstein 不等式 \(|Q'(x)| \leq O(d/\sqrt{1 - x^2})\)（当 \(\sqrt{1 - x^2} > 1/d\) 时），可得 \(d \geq \Omega(\sqrt{tn})\)。当 \(d < \sqrt{n}\) 时，Coppersmith - Rivlin 结果保证 \(|Q(\xi)| \leq 2^{O(\sqrt{d})} = O(1)\) 对于所有 \(\xi \in [-1,1]\)；但对于较大的 \(d\)，需要进行复杂的情况分析。 #### 2. Minsky - Papert CNF 的阈值度下界 Minsky - Papert CNF 为 \(AND_m \circ OR_b\)，之前已建立了两种不同的上界。Minsky 和 Papert 给出了一个经典的对称化论证，表明至少在 \(O(\sqrt{\log m})\) 因子范围内，其中一种逼近技术总是最优的。 定理：\(deg_{\pm}(AND_m \circ OR_b) \geq \Omega(\min\{m, b^{1/2}\})\)。 其证明过程如下： - 首先使用引理 5.7（对定理 5.2 的推广），若 \(p\) 符号表示 \(AND_m \circ OR_{4m^2}\)，则存在多项式 \(q: ([4m^2]*)^m \to \mathbb{R}\)，使得 \(q(t_1, \cdots, t_m) > 0\) 当且仅当 \(t_j = 0\) 对于某个索引 \(i\) 成立。 - 然后将 \(q\) 再次对称化为单变量多项式 \(q: [2m]^* \to \mathbb{R}\)，该多项式在输入从 \(0\) 增加到 \(2m\) 时符号改变 \(m\) 次，所以其度至少为 \(m\)，进而原多项式 \(p\) 的度至少为 \(m\)。 具体步骤如下： - 设 \(p\) 是 \(AND_m \circ OR_b\) 的符号表示多项式，\(q\) 是由引理 5.7 保证存在的 \(m\) 变量多项式。定义单变量多项式 \(q(t) = q((t - 0)^2, (t - 2)^2, \cdots, (t - 2(m - 1))^2)\)。 - 当 \(t\) 为奇数时，\(q\) 的输入均大于 \(0\)，所以 \(q(t) < 0\)；当 \(t\) 为偶数时，\(q\) 的输入有一个为 \(0\)，所以 \(q(t) > 0\)。因此，\(q\) 在 \(0\) 到 \(2m - 1\) 之间符号改变至少 \(2m - 1\) 次，其度至少为 \(2m - 1\)。又因为 \(deg(q) \leq 2deg(p)\)，所以 \(p\) 的度至少为 \(m\)。 以下是 Minsky - Papert CNF 阈值度下界证明的流程图： ```mermaid graph TD; A[开始] --> B[设p符号表示AND_m o OR_b]; B --> C[根据引理5.7得到q]; C --> D[定义单变量多项式q(t)]; D --> E[分析t为奇数时q(t)的符号]; D --> F[分析t为偶数时q(t)的符号]; E --> G[确定q符号改变次数]; F --> G; G --> H[得出q的度至少为2m - 1]; H --> I[根据deg(q) <= 2deg(p)得出p的度至少为m]; I --> J[结束]; ``` #### 3. 对称化方法的应用 对称化方法在计算复杂性理论中有广泛的应用： - **学习理论**：低阈值度的函数类在 PAC 模型中有学习算法。Klivans 和 Servedio 证明了任何多项式规模的 CNF 的阈值度至多为 \(O(n^{1/3})\)，从而得到了一个在 \