Problem Detail: 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 Ask a Question Download Related Notes/Documents
