On the unique shortest lattice vector problem

Abstract

The problem of deciding whether a given rotational lattice L has a vector of length less than some given value r is shown to be NP-hard. This problem is even under the premise that L has exactly zero or one vector of length less than r. The premise is also under randomized conditions.