MP16 N EAREST L ATTICE V ECTOR

     
• I NSTANCE : Lattice basis where , a point , and a positive integer p .
• S OLUTION : A vector b in the lattice, where .
• M EASURE : The distance between and b in the norm.

• Bad News: Not in A PX [ 21 ].
• Comment: Not approximable within for any unless NP QP [ 22 ]. The special case where is the zero vector and is not approximable within for any unless NP QP [ 21 ].