Consider some lattice in R^n.
Take some point "P" in R^n (which does not belong to this lattice in general).
What are the algorithms to find some nearest lattice point to "P" ?
"Nearest" – means in the sense of the standard Eucleadian distance.
Lattice – means the standard thing – takes some vectors h_1 … h_n and consider all their combinatioons with INTEGER coefficients. (Let us assume that h_i are independent and their number is exactly the dimension of the ambient R^n).
I think this should pretty well-studied question…
Can someone recommend some good literature for it ?
What are the general results known for it ?
What are the algorithm complexity ?
Is it NP problem ?
Best Answer
This problem is often called the "closest vector problem" for lattices (especially by people in theoretical computer science). The real issue is what sort of lattice you have. For example, for the integer lattice $\mathbb{Z}^n$ the problem is easy, and it's not too hard to do it for other famous lattices, for example root lattices. So if you have a specific, not very complicated lattice in mind, you shouldn't necessarily despair.
However, for an arbitrary lattice it's hard. The strongest result I know of offhand is that Dinur, Kindler, Raz, and Safra proved that it is NP-hard to approximate the distance to the closest lattice point by a factor of $n^{c/\log \log n}$ in $n$ dimensions (Combinatorica 23 (2003), 205–243); however, it may have been slightly improved since then. Using LLL lattice basis reduction, you can get an approximation to within a slightly subexponential factor in polynomial time.
For a good overview, see the book Complexity of lattice problems: a cryptographic perspective by Micciancio and Goldwasser.