It was shown in


P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short
vectors in a lattice


that the construction of a shortest nonzero vector of a Euclidean lattice w.r.t. the $L^{\infty}$-norm is NP-hard.


But for the $L^2$ norm, is this question still open? Can anyone explain the difficulty and progress in this problem?



Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?
The NP-hardness of the shortest vector problem in $L\_2$ norm is discussed in this 2015 [lecture](https://people.csail.mit.edu/vinodv/6876-Fall2015/L10.pdf) by Vinod Vaikuntanathan. An algorithm for this problem would give a *randomised* algorithm for any problem in NP.


The original reference is [The Shortest Vector Problem in $L\_2$ is NP-hard for Randomized Reductions](https://dl.acm.org/doi/pdf/10.1145/276698.276705) by Miklós Ajtai.


The problem remains NP-hard if the shortest vector must only be found within any constant factor (a result by [Subhash Khot](https://doi.org/10.1016/j.jcss.2005.07.002)).


This table from the lecture notes summarizes the situation. SVP$\_\gamma$ is the shortest vector problem within a factor $\gamma$, the $\ast$ refers to the randomized reduction, and "quasi" refers to super-polynomial (though still sub-exponential) scaling.


![](https://i.stack.imgur.com/BhHjm.png)
