On the unique shortest lattice vector problem

Authors
Kumar, SR Sivakumar, D
Citation
Sr. Kumar et D. Sivakumar, On the unique shortest lattice vector problem, THEOR COMP, 255(1-2), 2001, pp. 641-648
Citations number
10
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
255
Issue
1-2
Year of publication
2001
Pages
641 - 648
Database
ISI
SICI code
0304-3975(20010328)255:1-2<641:OTUSLV>2.0.ZU;2-B
Abstract
We show that the problem of deciding whether a given rational lattice L has a vector of length less than some given value r is NP-hard, even under the promise that L has exactly zero or one vector of length less than r. (C) 2 001 Published by Elsevier Science B.V.