5
$\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$
3
  • 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$ Dec 4, 2014 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, 2014 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$ Dec 5, 2014 at 2:37

2 Answers 2

5
$\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$
0
$\begingroup$

There is a mismatch in terminology in your question. The problem you specify is known as the shortest vector problem (SVP). You called it the closest vector problem (CVP), but the CVP is something different.

If you are asking about the SVP, as your mathematical formulation implies, it is known to be NP-hard in the $L_\infty$ norm but not known to be NP-hard in any other norm. The proof is found in the paper Another NP-Complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice, by P. van Emde Boas. Confusingly, the terminology has changed over time: van Emde Boas calls this problem the "closest vector problem", but under modern naming conventions, this is known as the SVP in $L_\infty$ norm. That said, there is strong evidence that the SVP in $L_2$ norm is almost certainly hard, even though we do not have a proof that it is NP-hard.

If you are truly asking about the CVP, then your mathematical formulation is incorrect, under the standard naming terminology that is accepted today. The CVP is known to be NP-complete in the $L_2$ norm (and possibly in other norms as well). This proof is also due to van Emde Boas. Confusing, he calls this problem the "nearest vector" problem, but under modern naming conventions, this is known as the CVP in $L_2$ norm.

The difference between the CVP vs SVP is that the SVP asks to find the shortest lattice vector, i.e., the lattice vector that is closest to $0$ (the all-zeros vector); in contrast, the CVP is more general, as the input includes a vector $v$, and the goal is to find the lattice vector that is closest to $v$. So CVP is at least as hard as SVP. See https://en.wikipedia.org/wiki/Lattice_problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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