Note on the shortest lattice vector problem

Abstract

The problem of deciding whether a given rational lattice L has a vector of length less than some given value r is addressed. It is demonstrated that this problem is NP-hard under randomized reductions, even under the promise that L has exactly zero or one vector of length less than r.