Euclidean SVP is deterministically NP-hard to approximate within any constant factor

技术摘要：欧几里得 SVP 近似问题的确定性 NP-困难性

问题陈述
本文探讨了欧几里得最短向量问题（SVP）的计算复杂度。具体而言，它研究了 $\rho$-GapSVP 问题：给定一个整格基和阈值 $d$，区分以下两种情况：是否存在最短非零向量长度 $\lambda_2(L) \le d$（YES），以及是否 $\lambda_2(L) > \rho d$（NO），其中 $\rho > 1$ 为常数近似因子。

在此项工作之前，欧几里得 SVP 近似问题的确定性 NP-困难性仅限于因子 $\rho < \sqrt{2}$。虽然随机归约已在编码理论中建立了任意常数因子（Khot [22]）甚至近多项式因子的硬度（Haviv 和 Regev [19]），但将这些结果在欧几里得空间中进行去随机化是一个维持了十多年的开放性挑战。欧几里得范数在张量积下缺乏类似于编码理论中汉明距离的乘法性质，这是主要的障碍。

方法论
作者构建了一个从 NP 完全问题到任何常数 $\rho > 1$ 的欧几里得 $\rho$-GapSVP 的确定性多项式时间单向归约（many-one reduction）。证明策略依赖于三个组成部分：

1. 确定性二元 $\ell_1$ 间隙构造：
   作者首先构造了一个在 $\ell_1$ 范数下具有“二元间隙”的格。他们结合了来自 Gap Exact Set Cover 的确定性归约与一个 Reed–Solomon 本地稠密格 模块。

   • 集合覆盖（Set Cover）归约（基于 Micciancio [27] 和 Bennett–Peikert [9]）创建了一个源实例，其中 YES 实例产生低权重的二元向量，而 NO 实例则迫使所有非零整数向量具有高支撑集。
   • Reed–Solomon 模块（源自作者之前的研究 [36]）确保对于任何给定的二元投影，在特定的陪集中都存在一个二元且其 $\ell_1$ 范数略高于格最小值的格向量。
   • 通过块嵌入（block embedding）将两者结合，他们生成了一个格 $L$ 和阈值 $d$，使得：
     • YES： 存在二元向量 $y \in L \cap \{0,1\}^N$，满足 $\|y\|_1 < d$。
     • NO： 对于所有非零向量 $x \in L$，满足 $\|x\|_1 \ge \eta d$，其中 $1 < \eta < 2$ 是一个固定常数。

2. 精确 $\ell_1$ 张量恒等式：
   一个关键的理论贡献是证明了整格的最小 $\ell_1$ 范数在张量积下具有乘法性。

   • 不同于欧几里得范数（$\ell_2$）（在 $\ell_2$ 中，张量积格 $L_1 \otimes L_2$ 中的最短向量不一定是纯张量，因此 $\lambda_2(L_1 \otimes L_2) \neq \lambda_2(L_1)\lambda_2(L_2)$），$\ell_1$ 最小值满足精确恒等式：
     $$\lambda(L_1 \otimes \dots \otimes L_t) = \prod_{i=1}^t \lambda(L_i)$$
   • 该结果通过将格的 $\ell_1$ 最小值与整数剩余环上商码的最小 Lee 权重联系起来得到建立。作者利用 Ojiro–Matsui 的 Lee 权重乘积公式 [29]，证明了这种乘法性对于全秩格成立，并通过补全论证将其扩展到任意秩的格。

3. 张量放大：
   作者对步骤 1 中构造的基础格 $L$ 进行 $t$ 次张量幂运算。

   • 在 YES 情况中，向量 $y^{\otimes t}$ 保持为二元。由于二元向量满足 $\|v\|_2^2 = \|v\|_1$，其欧几里得长度变为 $\|y^{\otimes t}\|_2 = \|y\|_1^{t/2} < d^{t/2}$。
   • 在 NO 情况中，$\ell_1$ 范数的乘法性质确保了 $\lambda(L^{\otimes t}) = \lambda(L)^t \ge (\eta d)^t$。利用不等式 $\|x\|_2 \ge \|x\|_1^{1/2}$（对于整数向量），其欧几里得长度被下界限制为 $(\eta d)^{t/2}$。
   • 最终的欧几里得近似间隙为 $\eta^{t/2}$。通过选择足够大的常数 $t$，该间隙可以超过任何预设的常数 $\rho$。

主要结果

• 定理 1.2（主定理）： 对于每个常数 $\rho > 1$，欧几里得 $\rho$-GapSVP 在确定性多项式时间单向归约下是 NP-困难的。这为 Khot 的随机化定理提供了确定性对应版本。
• 定理 1.4（所有有限范数）： 该结果扩展到了所有固定的有限 $\ell_p$ 范数（$1 \le p < \infty$）。对于任何固定的 $p$ 和常数 $\rho > 1$，$\rho$-GapSVP$_p$ 是确定性 NP-困难的。
• 定理 1.5（维度相关区间）： 通过允许张量阶数 $t$ 随输入规模增长（而非作为固定常数），作者推导出了此前仅通过随机归约已知的维度相关硬度区间：
  • 拟多项式时间归约： 对于因子 $2^{(\log n)^{1-\varepsilon}}$ 的硬度。
  • 亚指数时间归约： 对于因子 $n^{c/\log \log n}$ 的硬度。

意义与主张
本文声称解决了格计算理论中的一个长期开放问题，即通过移除在证明任意常数因子欧几里得 SVP 近似问题的 NP-困难性时对随机性的需求。

• 去随机化： 本工作成功实现了欧几里得 SVP 归约的去随机化，由于在欧几里得空间中构造确定性本地稠密格的难度，这一任务此前一直难以实现。
• 方法论转向： 证明并未尝试对 Khot 的构造进行逐行去随机化。相反，它引入了一种新的结构化方法：使用确定性二元模块创建一个 $\ell_1$ 间隙，然后利用 $\ell_1$ 范数在张量积下的精确乘法性，将此间隙放大到欧几里得域中。
• 编码理论类比： 本文强调了格问题与编码理论之间的深层联系。正如线性码的最小汉明距离在张量积下具有乘法性，作者展示了整格的最小 $\ell_1$ 范数（通过 Lee 度量）也具有该性质，从而允许将编码理论中的放大技术转移到格理论中。
• 与前人工作的比较： 作者指出，虽然 Hair 和 Sahai [18] 最近获得了任意常数因子的确定性硬度，但其结果依赖于 PCP 方法和亚指数时间归约。本文通过多项式时间归约改进了这一点。

文章总结道，虽然张量放大法存在天然上限（产生因子为 $n^{o(1)}$ 而非固定 $\varepsilon$ 下的 $n^\varepsilon$），但它成功建立了欧几里得 SVP 及所有有限 $\ell_p$ 范数的常数因子近似的确定性硬度。