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 way out of Manchester is notoriously a bottle of Gordon’s gin; out of any businessman’s life there is the mirage of Paris; out of Paris, or mediocrity of talent and imagination, there are all the drugs, from subtle, all-conquering opium to cheating, cozening cocaine.”
—William Bolitho (1890–1930)
“Only in the problem play is there any real drama, because drama is no mere setting up of the camera to nature: it is the presentation in parable of the conflict between Man’s will and his environment: in a word, of problem.”
—George Bernard Shaw (1856–1950)