The shortest vector problem (SVP) asks to find a nonzero vector in a lattice. The problem can be defined with respect to any norm, but the Euclidean norm is the most common. In the approximation version of SVP, the goal is to find a nonzero lattice vector of length at most g times the length of the optimal solution, where the approximation factor g is usually a function of the lattice dimension.
There are three main approaches to the exact solution of SVP in n-dimensional lattices:
Approximation algorithms for SVP are based on basis reduction techniques, and achieve approximation factors as small as in polynomial time.
Approximating SVP in the Euclidean norm is NP-hard (under randomized reductions) for any constant approximation factor
Stronger results are known in the norm, where SVP in is known to be NP-hard under deterministic reductions for quasi polynomial approximation factors .
Approximate SVP is in coNP for factors, and in coAM for factors. So, it is not NP-hard for such factors, under standard complexity assumptions.
Lattice problems in NP intersect coNP (Aharonov & Regev, J. ACM 52:749-765, 2005)
On the limits of nonapproximability of lattice problems (Goldreich & Goldwasser, J. Comp. Sys. Sci., 60:540-563, 2000)
Finding a polynomial space algorithm to solve SVP in single exponential time . All currently known algorithms running in single exponential time make use of exponential space too. The best known running time for polynomial space algorithms is given by Enumeration, which runs in superexponential time .
Proving the NP-hardness of SVP in the Euclidean norm (even in its exact version) under deterministic reductions. All currently known reductions proving the NP-hardness of SVP in the euclidean norm (in its exact or approximate version) are randomized. For recent progress towards a deterministic proof see
Proving the NP-hardness of SVP within polynomial factors for some small .
Approximating SVP in polynomial time within some large polynomial factor .