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?
Asked By : Jernej
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33828
0 comments:
Post a Comment
Let us know your responses and feedback