Approximating the SVP to within a factor (1-1/dim/sup ε/) is NP-hard under randomized conditions
Jin‐Yi Cai, Ajay Nerurkar · 2002
Recently M. Ajtai showed that to approximate the shortest lattice vector in the l/sub 2/-norm within a factor (1+2(-dim/sup k/)), for a sufficiently large constant k, is NP-hard under randomized reductions. We improve this result to show that to approximate a shortest lattice vector within a factor (1+dim/sup -/spl epsiv//), for any /spl epsiv/>0, is NP-hard under randomized reductions. Our proof also works for arbitrary l/sub p/-norms, 1/spl les/p