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: How to find nearest lattice point to given point in R^n ? Is it NP ? How to find nearest lattice point to given point in R^n ? Is it NP ?
Lattice reduction in R^3 (R^4) or what is fundamental domain for SL(3,Z) , (SL(4,Z)) ?Lattice reduction in R^3 (R^4) or what is fundamental domain for SL(3,Z) , (SL(4,Z)) ?
How "often" does LLL-reduction produce "optimal" result ? Is there condition (or informal understanding) on lattice that it LLL is optimal ? How "often" does LLL-reduction produce "optimal" result ? Is there condition (or informal understanding) on lattice that it LLL is optimal ?
