GapSVP
The problem consists of differentiating between the instances of SVP in which the answer is at most 1 or larger than, where can be a fixed function of, the number of vectors. Given a basis for the lattice, the algorithm must decide whether or . Like other promise problems, the algorithm is allowed to err on all other cases.
Yet another version of the problem is for some functions . The input to the algorithm is a basis and a number . It is assured that all the vectors in the Gram–Schmidt orthogonalization are of length at least 1, and that and that where is the dimension. The algorithm must accept if, and reject if . For large, the problem is equivalent to because a preprocessing done using the LLL algorithm makes the second condition (and hence, ) redundant.
Read more about this topic: Lattice Problem