A note on the shortest lattice vector problem
Ravi Kumar, D. Sivakumar · 2003
We show that the problem of deciding whether a given rational lattice L has a vector of length less than some given value r is NP-hard under randomized reductions, even under the promise that L has exactly zero or one vector of length less than r.