论文标题
为什么我们无法证明塞思·硬度是最接近的矢量问题！
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!
论文作者
论文摘要
最近的工作[BGS17，ABGS19]显示了CVP的Seth Hartness in $ \ ell_p $ norm，对于任何$ p $，都不是整数。通过将$ n $变量的$ k $ -sat减少到CVP，在等级$ n $的晶格中，这表明了这一结果。在这项工作中，我们显示出在$ \ ell_p $ norm中证明CVP的类似结果的障碍，其中$ p $是整数。我们表明，对于任何$ c> 0 $，如果对于每一个$ k> 0 $，则存在有效的降低，可以将$ k $ -sat的实例映射到$ n $变量上的$ n $变量的实例为CVP实例，以在最多$ n^{c} $中的euclidean Nord，$ n^{c} $的等级实例，然后$ n^{c} $，然后$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ conp} $ n poloys $我们证明，在额外的额外承诺下，对于所有规范，CVP的结果是类似的结果，即晶格中目标距离与晶格和最短的非零矢量的比率受$ exp（n^{o（o（1）}）的限制。 此外，我们证明，对于任何$ c> 0 $，以及任何甚至整数$ p $，如果对于每$ k> 0 $，则存在有效的降低，可以将$ n $变量上的$ k $ -sat实例映射到$ svp_p $实例中，最多是$ n^{c} $ n^{c} $ butse $ n^{ \ Mathsf {np/poly} $。 SVP的结果不需要任何额外的承诺。 虽然先前的结果表明$ \ ell_2 $ norm（Euclidean Norm）中的晶格问题比其他规范中的晶格问题容易，但这是显示这些问题之间分离的第一个结果。 我们通过使用Dell和Van Melkebeek [JACM，2014]的结果来实现这一目标，这是由于不可能将任意的$ k $ -sat实例压缩到一串长度$ \ MATHCAL {O}（n^{k-ε}）$中的降低中。除了CVP外，我们还表明，使用相似技术的子集和子集问题相同的结果。
Recent work [BGS17,ABGS19] has shown SETH hardness of CVP in the $\ell_p$ norm for any $p$ that is not an even integer. This result was shown by giving a Karp reduction from $k$-SAT on $n$ variables to CVP on a lattice of rank $n$. In this work, we show a barrier towards proving a similar result for CVP in the $\ell_p$ norm where $p$ is an even integer. We show that for any $c>0$, if for every $k > 0$, there exists an efficient reduction that maps a $k$-SAT instance on $n$ variables to a CVP instance for a lattice of rank at most $n^{c}$ in the Euclidean norm, then $\mathsf{coNP} \subset \mathsf{NP/Poly}$. We prove a similar result for CVP for all even norms under a mild additional promise that the ratio of the distance of the target from the lattice and the shortest non-zero vector in the lattice is bounded by $exp(n^{O(1)})$. Furthermore, we show that for any $c> 0$, and any even integer $p$, if for every $k > 0$, there exists an efficient reduction that maps a $k$-SAT instance on $n$ variables to a $SVP_p$ instance for a lattice of rank at most $n^{c}$, then $\mathsf{coNP} \subset \mathsf{NP/Poly}$. The result for SVP does not require any additional promise. While prior results have indicated that lattice problems in the $\ell_2$ norm (Euclidean norm) are easier than lattice problems in other norms, this is the first result that shows a separation between these problems. We achieve this by using a result by Dell and van Melkebeek [JACM, 2014] on the impossibility of the existence of a reduction that compresses an arbitrary $k$-SAT instance into a string of length $\mathcal{O}(n^{k-ε})$ for any $ε>0$. In addition to CVP, we also show that the same result holds for the Subset-Sum problem using similar techniques.
