A relation of primal-dual lattices and the complexity of shortest lattice vector problem

摘要

We give a simplified proof of a theorem of Lagarias, Lenstra and Schnorr [17] that the problem of approximating the length of the shortest lattice vector within a factor of Cn, for an appropriate constant C, cannot be NP-hard, unless NP = coNP. We also prove that the problem of finding a n(1/4)-unique shortest lattice vector is not NP-hard under polynomial time many-one reductions, unless the polynomial time hierarchy collapses. (C) 1998-Elsevier Science B.V. All rights reserved. [References: 24]