Lattice Problem - Shortest Vector Problem (SVP)

Shortest Vector Problem (SVP)

In SVP, a basis of a vector space V and a norm N (often L2) are given for a lattice L and one must find the shortest non-zero vector in V, as measured by N, in L. In other words, the algorithm should output a non-zero vector v such that .

In the -approximation version, one must find a non-zero lattice vector of length at most .