ABSTRACT
In this chapter we present the proof by van Emde Boas [144] that the problem of finding a shortest lattice vector with respect to the max norm on Rn is NPcomplete. By the max norm we mean as usual
|x|∞ = max (|x1|, |x2|, . . . , |xn|) for x = [x1, x2, . . . , xn] ∈ Rn .
