Question

Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). The problem is to find "nearest" lattice point. The problem is known NP-hard in general it is named "closest vector problem".

Is it correct that "hardness" comes from the "lattice reduction" step ? I mean if in our lattice we can easily get the shortest and any other vector or basis we want then problem becomes not NP-hard ?

Some related posts: http://mathoverflow.net/questions/61897/how-to-find-nearest-lattice-point-to-given-point-in-rn-is-it-np

http://mathoverflow.net/questions/61933/lattice-reduction-in-r3-r4-or-what-is-fundamental-domain-for-sl3-z-sl4

http://mathoverflow.net/questions/61945/how-often-does-lll-reduction-produce-optimal-result-is-there-condition-or

Answer 1

It actually remains hard, although not as hard. See the paper Hardness of approximating the closest vector problem with pre-processing by Alekhnovich, Khot, Kindler, and Vishnoi (FOCS 2005, http://www.math.ias.edu/~misha/papers/cvpp.pdf). They show that even if you are allowed to do arbitrary pre-processing after having been given the lattice basis but before seeing the target vector, you still can't get a better approximation factor than $(\log n)^{1/2-\varepsilon}$, assuming your calculations after seeing the target vector must run in polynomial time, and assuming that there are no quasi-polynomial-time algorithms for NP.

However, you do get real benefit from being able to do lattice basis reduction in advance (not just LLL reduction, but something more computationally intensive). For example, Lagarias, Lenstra, and Schnorr showed that using Korkine-Zolotarev reduction, you could get an $n^{1.5}$ approximation factor (Combinatorica 10 (1990), 333–348). In FOCS 2004, Aharonov and Regev got a $\sqrt{n/\log n}$ approximation factor with pre-processing. However, in all these algorithms the pre-processing requires more than polynomial time.