# NP completeness of closest vector problem

Let $\mathcal{B} = \{v_1,v_2,\ldots,v_k\} \in \mathbb{R}^n$ be linearly independent vectors.

Recall that the integer lattice of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations of elements of $\mathcal{B}$ using only integers as coefficients. That is $$L(\mathcal{B}) = \{ \sum_{i=1}^k c_i b_i \mid c_i \in \mathbb{Z}\}.$$

The closest vector problem asks us to find a nonzero vector $v \in L(\mathcal{B})$ such that $||v||$ is minimized.

It is apparently well known that this problem is NP-complete though I was not able to find a reduction to any of the "well known" NP-complete problems.

The first proof of this claim seems to be in P. van Emde Boas. "Another NP-complete problem and the complexity of computing short vectors in a lattice"., but I cannot find a copy of this paper.

Can someone give a polynomial reduction of some well known NP complete problem to the closest vector problem?

• I found the original paper; staff.fnwi.uva.nl/p.vanemdeboas/vectors/abstract.html - apparently it is by reduction from a partition variant. – Tom van der Zanden Dec 4 '14 at 10:43
• @TomvanderZanden Unfortunatelly I think this paper does not solve the named problem. Citing the introduction: "we conjecture that the same holds for the closely related shortest vector problem, but our proof technique fails to prove this result as well." – Jernej Dec 4 '14 at 16:54
• On page 6 (staff.fnwi.uva.nl/p.vanemdeboas/vectors/page6.html) it says (2nd paragraph): "In this section we draw attention to a negative and a positive result. The negative result is given by Theorem 2 which indicates that for the $L^\infty$-metric the problem of computing a shortest non-zero vector in a lattice is NP-hard." – Yuval Filmus Dec 5 '14 at 2:37

As far as I know, it is not known that the shortest vector problem is NP-hard for any $L^p$ norm other that $L^\infty$. It is known that the shortest vector problem is "NP-hard under randomized reductions" for all $L^p$, a result first proved by Ajtai. See for example Miccanccio's paper and the results he references. Since then better inapproximability results have been obtained, but as far as I can tell nobody could prove an unconditional NP-hardness result.