The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)
The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)
复制标题
DOI：
10.1145/276698.276705
复制
发表时间：
1998-05
期刊：
影响因子：
--
通讯作者：
M. Ajtai
中科院分区：
文献类型：
--
作者：
M. Ajtai
我们证明了具有La范数的格中的最短向量问题对于随机约简是NP难的。此外，我们还证明了存在一个绝对常数E>；0，使得找到一个比最短的非零向量长不超过1+2‘**(相对于ES范数)的向量对于随机约简也是NP-难的。对于随机约简，相应的决策问题是NP完全的。1.引言。R*中的格是其固定的线性无关向量的所有整数线性组合的集合。范数为L范数的格求最短非零向量的问题被Van Emde Boas证明是NP难的。然而，对于LZ范数(或任何其他对于1 5p nL*a(其中n是格子的维度))，相应的问题是Np=co-Np。根据最近的一个结果是0。Goldreich和S.Goldwasser认为，即使对于q：=$，a-近似问题也不太可能是NP-困难的，因为这个问题是NP-tl-coam(见[GG])。本文证明了随机约简下的最短向量问题是NP-难的。也就是说，存在一个概率图灵机，它在多项式时间内将NP中的任何问题归结为最短向量问题的实例。换言之，这个概率规则机器可以在多项式时间内解决NP中的任何问题，只要它可以使用一个预言来返回最短向量问题的解(通过给出相应的格的基)，我们证明了对于1+2-*‘-近似问题的结果，其中E>；0是足够小的绝对常数，n是格的维度。(最近蔡俊云和A.Nerurkar有…
We show that the shortest vector problem in lattices with La norm is NP-hard for randomized reductions. Moreover we also show that there is an absolute constant E > 0 so that to find a vector which is longer than the shortest non-zero vector by no more than a factor of 1 + 2'** (with respect to the Es norm) is also NP-hard for randomized reductions. The corresponding decision problem is NP-complete for randomized reductions. 1. Introduction. A lattice in R* is the set of all integer linear combinations of It fixed linearly independent vectors. T'he question of finding the shortest non-zero vector in a lattice with repsect to the L, norm was proved to be NP-hard by Van Emde Boas. However the corresponding problem for the Lz norm (or any other for 1 5 p nl*a (where n is the dimension of the lattice) than NP = co-NP. According to recent a result of 0. Goldreich and S. Goldwasser it is unlikeley that the a-approximation problem is NP-hard even for Q: = $, since this problem is in NP tl coAM (see [GG]). In this paper we show that the shortest vector problem is NP-hard for randomized reductions. That is, there is a prob-abilistic Turing-machine which in polynomial time reduces any problem in NP to instances of the shortest vector problem. In other words this probabilistic 'Ruing machine can solve in polynomial time any problem in NP, provided that it can use an oracle which returns the solution of the shortest vector problem if an instance of it presented (by giving a basis of the corresponding lattice). We prove the same result about the 1 + 2-*'-approximate problem where E > 0 is n sufficiently small absolute constant and n is the dimension ot the lattice. (Recently J.-Y. Cai and A. Nerurkar has …