3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I found the original paper; staff.fnwi.uva.nl/p.vanemdeboas/vectors/abstract.html - apparently it is by reduction from a partition variant. $\endgroup$ – Tom van der Zanden Dec 4 '14 at 10:43
  • $\begingroup$ @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." $\endgroup$ – Jernej Dec 4 '14 at 16:54
  • $\begingroup$ 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." $\endgroup$ – Yuval Filmus Dec 5 '14 at 2:37
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.