# On the shortest vector problem (is it $NP$-complete?)

Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum.

Has this been derandomized?

• I think this is still an open problem. Here is a reference from 2012, for example: theoryofcomputing.org/articles/v008a022/v008a022.pdf. This paper from 2014 mentions only randomized reductions arxiv.org/abs/1412.7994 – Sasho Nikolov Nov 21 '16 at 1:32
• @SashoNikolov thank you. one more small point to clarify. Does the SVP problem inherently have an unique solution or at least just at most a slowly growing number (that is do we have much choice in picking shortest basis upto signs)? – Turbo Nov 21 '16 at 4:47
• @SashoNikolov 'unique solution upto signs or at least just at most a slowly growing number upto signs'. – Turbo Nov 21 '16 at 5:19
• In the integer lattice $\mathbb{Z}^n$ the shortest nonzero vectors are the standard basis vectors (and their negations), which is $n$ vectors up to signs. I am not sure what the best upper bound on the number of shortest vectors is. – Sasho Nikolov Nov 21 '16 at 8:44
• see for example section 3.4. of this paper by Leech. – Sasho Nikolov Nov 21 '16 at 13:12