<p>Ajtai has shown that shortest vector problem is $NP$-hard by using <a href="http://www.csie.nuk.edu.tw/~cychen/Lattices/The%20shortest%20vector%20problem%20in%20L2%20is%20NP-hard%20for%20randomized%20reductions%20(extended%20abstract).pdf" rel="noreferrer">randomized reduction from subset sum</a>.</p>

<p>Has this been derandomized?</p>

CC BY-SA 3.0
2016-11-21T01:32:04.930Z
I think this is still an open problem. Here is a reference from 2012, for example: http://www.theoryofcomputing.org/articles/v008a022/v008a022.pdf. This paper from 2014 mentions only randomized reductions https://arxiv.org/abs/1412.7994
Sasho Nikolov
CC BY-SA 3.0
2016-11-21T04:47:34.730Z
@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
CC BY-SA 3.0
2016-11-21T05:19:09.050Z
@SashoNikolov 'unique solution upto signs or at least just at most a slowly growing number upto signs'.
Turbo
CC BY-SA 3.0
2016-11-21T08:44:26.043Z
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
CC BY-SA 3.0
2016-11-21T09:18:49.340Z
After some more thought: The number of shortest nonzero vectors in a lattice is at least (exactly?) the largest kissing number of a lattice packing of balls. This is known to be at least $2^{\Omega(\log^2 n)}$ in dimension $n$, and I think it is consistent with current knowledge that it may be exponential in $n$.
Sasho Nikolov
CC BY-SA 3.0
2016-11-21T09:37:20.063Z
@SashoNikolov great comment. Thank you but why does kissing number count shortest basis or if not why does it lower bound ?
Turbo
CC BY-SA 3.0
2016-11-21T09:40:15.953Z
@SashoNikolov also could you provide reference for the superpoly lower bound you are quoting?
Turbo
CC BY-SA 3.0
2016-11-21T11:15:19.450Z
for kissing numer SVP connection I see [here](http://perso.ens-lyon.fr/damien.stehle/downloads/SVPCVP.pdf). I still do not know the superpoly lower bound.
Turbo
CC BY-SA 3.0
2016-11-21T13:12:44.200Z
see for example section 3.4. of this [paper by Leech](https://cms.math.ca/openaccess/cjm/v16/cjm1964v16.0657-0682.pdf).
Sasho Nikolov
CC BY-SA 3.0
2016-12-21T17:11:36.863Z
@SashoNikolov: Everything you said is right. I think you should make your comments into an answer. A couple of comments: $\ell_\infty$-SVP is known to be NP-hard under deterministic reductions using a similar reduction to the one used to show NP-hardness for CVP. $\ell_p$-SVP is NP-hard even to approximate within any constant factor for any $p > 1$ (http://www.cs.nyu.edu/~khot/papers/j-svp.ps).
Huck Bennett
<np-hardness><np-complete><derandomization><lattice><integer-lattice>
On the shortest vector problem (is it $NP$-complete?)
Turbo
# On the shortest vector problem (is it $NP$-complete?)

(Asked by: username_0 on 2016-11-20)

Ajtai has shown that shortest vector problem is $NP$-hard by using [randomized reduction from subset sum](http://www.csie.nuk.edu.tw/~cychen/Lattices/The%20shortest%20vector%20problem%20in%20L2%20is%20NP-hard%20for%20randomized%20reductions%20(extended%20abstract).pdf).

Has this been derandomized?

**Tags:** np-hardness, np-complete, derandomization, lattice, integer-lattice
> **Comments:**
> **username_1**: I think this is still an open problem. Here is a reference from 2012, for example: http://www.theoryofcomputing.org/articles/v008a022/v008a022.pdf. This paper from 2014 mentions only randomized reductions https://arxiv.org/abs/1412.7994  
> **username_0**: @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)?  
> **username_0**: @SashoNikolov 'unique solution upto signs or at least just at most a slowly growing number upto signs'.  
> **username_1**: 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.  
> **username_1**: After some more thought: The number of shortest nonzero vectors in a lattice is at least (exactly?) the largest kissing number of a lattice packing of balls. This is known to be at least $2^{\Omega(\log^2 n)}$ in dimension $n$, and I think it is consistent with current knowledge that it may be exponential in $n$.  
> **username_0**: @SashoNikolov great comment. Thank you but why does kissing number count shortest basis or if not why does it lower bound ?  
> **username_0**: @SashoNikolov also could you provide reference for the superpoly lower bound you are quoting?  
> **username_0**: for kissing numer SVP connection I see [here](http://perso.ens-lyon.fr/damien.stehle/downloads/SVPCVP.pdf). I still do not know the superpoly lower bound.  
> **username_1**: see for example section 3.4. of this [paper by Leech](https://cms.math.ca/openaccess/cjm/v16/cjm1964v16.0657-0682.pdf).  
> **username_2**: @SashoNikolov: Everything you said is right. I think you should make your comments into an answer. A couple of comments: $\ell_\infty$-SVP is known to be NP-hard under deterministic reductions using a similar reduction to the one used to show NP-hardness for CVP. $\ell_p$-SVP is NP-hard even to approximate within any constant factor for any $p > 1$ (http://www.cs.nyu.edu/~khot/papers/j-svp.ps).  

---

## 0 answers

