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 .
Read more about this topic: Lattice Problem
Famous quotes containing the words shortest and/or problem:
“The shortest route is not the most direct one, but rather the one where the most favorable winds swell our sails:Mthat is the lesson that seafarers teach. Not to abide by this lesson is to be obstinate: here, firmness of character is tainted with stupidity.”
—Friedrich Nietzsche (1844–1900)
“You are a problem and rune,
you are mystery;
writ on a stone.”
—Hilda Doolittle (1886–1961)