碰撞与排列测试问题的近似度分析

### 碰撞与排列测试问题的近似度分析 #### 1. 定理 8.3 的证明 为了说明如何根据向量 \(z\) 的元素计算方程 (8.14) 的右侧，我们通过一个例子来进行阐述。假设 \(g(y) = g(1 - y_{1,1})(1 - y_{1,2})(1 - y_{2,3})\)。 - \(Pr[y_{1,1} = -1]\) 表示在范围项 1 的 \(z_1\) 次出现中，有一次出现在输入列表索引 1 处的概率，该概率恰好为 \(z_1/N\)。 - 在 \(y_{1,1} = -1\) 的条件下，\(y_{1,2} = -1\) 的概率是在输入列表中剩余的 \(z_1 - 1\) 次范围项 1 的出现中，有一次出现在输入列表索引 2 处的概率，此概率为 \((z_1 - 1)/(N - 1)\)。 - 在 \(y_{1,1} = -1\) 和 \(y_{1,2} = -1\) 的条件下，\(y_{2,3} = -1\) 的概率是在输入列表中范围项 2 的 \(z_2\) 次出现中，有一次出现在输入列表索引 3 处的概率，该概率为 \(z_2/(N - 2)\)。 因此，方程 (8.14) 的右侧等于 \(\frac{z_1(z_1 - 1)z_2}{N(N - 1)(N - 2)}\)，这是关于 \(z = (z_1, \cdots, z_r)\) 的总次数为 3（即 \(deg(g)\)）的多项式。 一般情况下，设 \(A_{i}\) 为某个集合，方程 (8.14) 的右侧等于： \[ \sum_{i\in[R]} C_i \cdot z_i \cdot (z_i - 1)\cdots (z_i - |A_i| + 1) \] 其中 \(C_i = \frac{1}{(N - |A_{<i}|)(N - |A_{<i}| - 1)\cdots (N - |A_{<i}| - |A_i| + 1)}\)。这个表达式中的每个因子都是 \(z_i \cdot (z_i - 1)\cdots (z_i - |A_i| + 1)\) 乘以某个与 \(z\) 无关的因子 \(C_i\)，因此它是关于 \(z = (z_1, \cdots, z_r)\) 的总次数至多为 \(\sum_{i\in[R]} |A_i| = d\) 的多项式。 为了证明完整的引理，我们引入了 \(SURJ\) 的一个变体 \(dSURJ\)。\(dSURJ\) 通过添加一个“虚拟范围元素”将 \(SURJ\) 的范围扩展了一个，该虚拟范围元素在输入列表中的存在或缺失不影响输出。也就是说，\(dSURJ\) 测试除指定虚拟范围元素之外的每个范围元素是否至少在输入列表中出现一次。 接下来进行两步分析： - **第一步**：证明近似 \(dSURJ\) 并不比近似 \(SURJ\) 本身更难。任何用于 \(SURJ\) 的 \(d\) 度 \(\epsilon\) - 近似多项式都可以转换为用于 \(dSURJ\) 的多项式。具体来说，这种转换是将虚拟范围元素的一个副本“硬编码”到 \(SURJ\) 的输入列表中，使得虚拟范围元素在 \(SURJ\) 的“真实”输入列表中的存在或缺失不再影响其输出。 - **第二步**：证明在一个对数因子的范围内，任何用于 \(dSURJ\) 的近似多项式都能产生一个用于 \((AND_R \circ OR_V)^{\neg V}\) 的近似多项式。这两步共同表明 \(deg_{\epsilon}(SURJ) > deg_{\epsilon}(dSURJ) > \Omega (deg_{\epsilon} ((AND_R \circ OR_V)^{\neg V}))\)。 为了证明第二步，我们应用之前的论证得出，任何用于 \(dSURJ\)（具有 \(R\) 个非虚拟范围元素）的近似多项式都意味着对 \((AND_R \circ OR_V)^{\neg V}\) 的一个轻微修改（记为 \(F_{=N}\)）的近似。在 \(F_{=N}\) 中，有 \(R + 1\) 个而不是 \(R\) 个 \(OR_V\) 的副本，但最后一个 \(OR_V\) 的副本被函数忽略，这与 \(dSURJ\) 忽略虚拟范围元素的方式相对应。 最后，我们需要证明 \(deg_{\epsilon}(F_{=N}) > deg_{\epsilon} ((AND_R \circ OR_V)^{\neg V})\)。设 \(p: \{ -1, 1\}^{N(R + 1)} \to \mathbb{R}\) 是一个总次数为 \(d\) 的多项式，它 \(\epsilon\) - 近似 \(F_{=N}\)。我们将 \(p\) 转换为一个相同次数的 \(\epsilon\) - 近似多项式，用于 \((AND_R \circ OR_V)^{\neg}\)。具体做法是考虑 \(p\) 的块式 Minsky - Papert 对称化，即一个总次数至多为 \(d\) 的多项式 \(q(z_1, \cdots, z_{r + 1}) : (\binom{[N]}{*})^R \to \mathbb{R}\)，对于输入 \(z_1, \cdots, z_{r + 1} \in (\binom{[N]}{*})^R\)，它输出 \(p\) 在所有输入上的平均值，其中第 \(i\) 个 \(OR_V\) 的副本输入的汉明重量为 \(i\)。 下面是这个过程的流程图： ```mermaid graph TD; A[开始] --> B[定义g(y)并计算概率]; B --> C[得出方程(8.14)右侧表达式]; C --> D[引入dSURJ]; D --> E[第一步：转换SURJ多项式到dSURJ]; E --> F[第二步：由dSURJ多项式得到F=N近似]; F --> G[证明deg(F=N) > deg((AND_R o OR_V)^¬V)]; G --> H[结束]; ``` #### 2. 碰撞与排列测试问题的近似度 设 \(n = N \log R\)，其中 \(N\) 为偶数，\(R\) 是 2 的幂。碰撞问题和排列测试问题（PTP）的输入是一个大小为 \(N\) 且取值范围为 \(R\) 的数字列表。 - **碰撞问题**：要区分一对一列表和二对一列表。碰撞问题的近似度是满足以下条件的多项式 \(p: \{ -1, 1\}^n \to \mathbb{R}\) 的最小次数： - 对于一对一输入 \(x\)，\(p(x) \in [2/3, 4/3]\)。 - 对于二对一输入 \(x\)，\(p(x) \in [-4/3, -2/3]\)。 - 其他情况下，\(|p(x)| \leq 4/3\)。 - **排列测试问题（PTP）**：区分一对一输入和与任何一对一输入距离较远的输入。在频率向量表示中，PTP 的近似度是满足