CVP

• Decisional, optimization, and search versions are (polynomial) equivalent.
• CVP is NP-complete (reduction from subset-sum problem).
• Given an oracle to $CVP_\gamma$, it is possible to solve $SVP_\gamma$ in polynomial time.
• Approximate CVP with factor $\log^c (n)$ is NP-Hard for any $\ell_p$ norm. [MC02, chapter 3]
• Approximate CVP in any $\ell_p$ norm with factor $< (5/3) ^ {\frac 1 p}$ is NP-Hard. [MC02, chapter 3]
• Approximate CVP with factors bigger than $O\left(\frac{ \sqrt{n} } {\log{n}} \right)$ is not expected to be NP-Hard. [MC02, chapter 9]

References

• [MC02] Complexity of Lattice Problems: A Cryptographic Perspective. By Daniele Micciancio and Shafi Goldwasser (2002)"