<p>Berlekamp, McEliece and Van Tilborg 
[On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)]
proved that deciding if a binary code contains a code word of weight $w$ is NP-complete. In <a href="http://statweb.stanford.edu/~cgates/PERSI/papers/85_04_radon.pdf" rel="nofollow">http://statweb.stanford.edu/~cgates/PERSI/papers/85_04_radon.pdf</a>
Diaconis and Graham prove that deciding if a binary code of length $2m$ contains a code word of weight $n$ is NP-complete. </p>

CC BY-SA 3.0
2015-04-08T21:13:53.020Z
Neither of those papers solves the OP's question. The first proof of the result that the OP is asking about was in Vardy's paper that Sasho links to in his comment above. It was a quite famous open question before then. The OP wants to know whether there is a simpler proof, which would necessarily have been discovered after Vardy's proof.
Peter Shor 
CC BY-SA 3.0
2015-04-08T21:15:57.273Z
To expand my previous comment, there is a difference between asking whether there is a codeword of weight ***exactly*** *w*, and whether there is a non-zero codeword of weight ***at most*** *w*. For example, *is there a simple cycle of length exactly k?* is NP-hard, but there's a polynomial-time algorithm to find the shortest simple cycle in a graph.
Peter Shor 
CC BY-SA 3.0
2015-04-08T21:03:17.363Z
2015-04-08T23:16:46.390Z
2015-04-08T23:16:46.390Z
Chris Godsil
<p>There happens to be this NP-complete question,</p>

<hr>

<p>Minimum-Distance-Over-$\mathbb{F}_{2^m}$</p>

<p>Given $w \in \mathbb{Z}^+$ and a $r \times n$ matrix $H$ over $\mathbb{F}_{2^m}$, is there a $x \in \mathbb{F}_{2^m}^n$ of weight $\leq w$ s.t $Hx=0$?</p>

<hr>

<ul>
<li><p>Is there some "easy" proof of this? (as opposed to say what I can partly fish out of this paper, <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542">http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542</a>) </p></li>
<li><p>Is there any variant of it where the hardness is true even if I assume that $H$ has at least $r$ linearly independent columns? (and such a condition gets automatically satisfied if the rows of $H$ define a code?) </p></li>
</ul>

CC BY-SA 3.0
2015-04-08T18:09:17.437Z
Maybe I don't understand your second question, but I think assuming that $H$ has $r$ linearly independent columns is without loss of generality. If $H$ has rank $r' < r$, then we can replace $H$ with a $r'\times n$ submatrix $H'$ whose rows form a basis for the rowspace of $H$. Then $H'x = 0$ if and only if $Hx = 0$ and $H'$ has rank $r'$ so it must have $r'$ linearly independent columns. As for the hardness reduction, I don't know what "easy" is, but did you read Vardy's paper http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542 ?
Sasho Nikolov
CC BY-SA 3.0
2015-04-08T18:33:44.910Z
@SashoNikolov Thanks for the explanation! I have indeed been trying to dig through Vardy's paper. But its quite a mess :D There is a complex network of reductions that its hardly clear to me as to which part is a proof of NP-hardness of this particular statement! Can you help decipher it? :D
Student
CC BY-SA 3.0
2015-04-09T20:59:16.467Z
For the future: We expect you to do research on your own before asking the question, and to tell us in the question what research you've done, what you've found, and what you know.  (For instance, if you already knew of that paper but had trouble understanding it, you should have mentioned this in the question -- leaving that out is a bit impolite to answerers who put in the effort only to have you tell them that you already knew that.)  Showing what you've already tried is in your interest as it ultimately makes it more likely you get the kind of answer you are looking for.
D.W.
CC BY-SA 3.0
2015-04-09T22:15:16.313Z
Thanks! I guess I should have made it more explicit that I am looking for an alternative reference or approach to the Vardy's paper - which I find to be quite convoluted to decipher!
Student
CC BY-SA 3.0
2015-05-09T23:16:09.043Z
Yes. Vardy's proof is a mess. A brilliant number theorist also told me this and he bets there is a simple proof. It has been a decade since he told me. I have not seen any new proof. Note that the analogous problem of shortest vector in real lattices has an interesting role in theory since it cannot be NP-complete unless some close to end of world scenarios happen. He also bet this problem is also NP complete (biased by mystical speculation of a Turing winner). If you find an alternate proof that illuminates lattice shortest vector scenario as well, your career will probably be set. Good Luck!
Turbo
CC BY-SA 3.0
2015-05-12T08:08:49.907Z
@Turbo Ajtai has shown that SVP is hard under randomized reductions and Micciancio has shown a constant hardness of approximation (also using a randomized reduction). Moreover, the randomization can be removed using a number theoretic conjecture. I think you are confused about the consequences of such a hardness proof: maybe you are thinking of an approximation version of SVP with polynomial approximation factors.
Sasho Nikolov
CC BY-SA 3.0
2015-05-12T08:19:10.833Z
http://cseweb.ucsd.edu/~daniele/Research/LatticeComp.html
Turbo
CC BY-SA 3.0
2015-05-12T08:20:59.123Z
I think may be he meant removing the number theoretic conjecture (since I remember vaguely about NP completeness not NP hardness).
Turbo
CC BY-SA 3.0
2015-05-12T09:04:09.653Z
Ok I think phrase "Note that the analogous problem of shortest vector in real lattices has an interesting role in theory since it cannot be NP-complete unless some close to end of world scenarios happen" is likely wrong however if I change to "Note that the analogous problem of shortest vector in real lattices is NP-complete is unknown" what I state seems likely.
Turbo
CC BY-SA 3.0
2015-05-13T09:05:57.987Z
However I am reasonably sure that there is a catch that this problem cannot be NP complete that easily (I forgot precise reasons since this was years past today).
Turbo
<cc.complexity-theory><np-hardness><prefix-free-code>
NP-hardness of minimum distance over a code
Student
# NP-hardness of minimum distance over a code

(Asked by: username_0 on 2015-04-08)

There happens to be this NP-complete question,

---

Minimum-Distance-Over-$\mathbb{F}\_{2^m}$

Given $w \in \mathbb{Z}^+$ and a $r \times n$ matrix $H$ over $\mathbb{F}\_{2^m}$, is there a $x \in \mathbb{F}\_{2^m}^n$ of weight $\leq w$ s.t $Hx=0$?

---

* Is there some "easy" proof of this? (as opposed to say what I can partly fish out of this paper, <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542>)
* Is there any variant of it where the hardness is true even if I assume that $H$ has at least $r$ linearly independent columns? (and such a condition gets automatically satisfied if the rows of $H$ define a code?)

**Tags:** cc.complexity-theory, np-hardness, prefix-free-code

> **Comments:**
> **username_1**: Maybe I don't understand your second question, but I think assuming that $H$ has $r$ linearly independent columns is without loss of generality. If $H$ has rank $r' < r$, then we can replace $H$ with a $r'\times n$ submatrix $H'$ whose rows form a basis for the rowspace of $H$. Then $H'x = 0$ if and only if $Hx = 0$ and $H'$ has rank $r'$ so it must have $r'$ linearly independent columns. As for the hardness reduction, I don't know what "easy" is, but did you read Vardy's paper http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542 ?  
> **username_0**: @SashoNikolov Thanks for the explanation! I have indeed been trying to dig through Vardy's paper. But its quite a mess :D There is a complex network of reductions that its hardly clear to me as to which part is a proof of NP-hardness of this particular statement! Can you help decipher it? :D  
> **username_2**: For the future: We expect you to do research on your own before asking the question, and to tell us in the question what research you've done, what you've found, and what you know.  (For instance, if you already knew of that paper but had trouble understanding it, you should have mentioned this in the question -- leaving that out is a bit impolite to answerers who put in the effort only to have you tell them that you already knew that.)  Showing what you've already tried is in your interest as it ultimately makes it more likely you get the kind of answer you are looking for.  
> **username_0**: Thanks! I guess I should have made it more explicit that I am looking for an alternative reference or approach to the Vardy's paper - which I find to be quite convoluted to decipher!  
> **username_3**: Yes. Vardy's proof is a mess. A brilliant number theorist also told me this and he bets there is a simple proof. It has been a decade since he told me. I have not seen any new proof. Note that the analogous problem of shortest vector in real lattices has an interesting role in theory since it cannot be NP-complete unless some close to end of world scenarios happen. He also bet this problem is also NP complete (biased by mystical speculation of a Turing winner). If you find an alternate proof that illuminates lattice shortest vector scenario as well, your career will probably be set. Good Luck!  
> **username_1**: @username_3 Ajtai has shown that SVP is hard under randomized reductions and Micciancio has shown a constant hardness of approximation (also using a randomized reduction). Moreover, the randomization can be removed using a number theoretic conjecture. I think you are confused about the consequences of such a hardness proof: maybe you are thinking of an approximation version of SVP with polynomial approximation factors.  
> **username_3**: http://cseweb.ucsd.edu/~daniele/Research/LatticeComp.html  
> **username_3**: I think may be he meant removing the number theoretic conjecture (since I remember vaguely about NP completeness not NP hardness).  
> **username_3**: Ok I think phrase "Note that the analogous problem of shortest vector in real lattices has an interesting role in theory since it cannot be NP-complete unless some close to end of world scenarios happen" is likely wrong however if I change to "Note that the analogous problem of shortest vector in real lattices is NP-complete is unknown" what I state seems likely.  
> **username_3**: However I am reasonably sure that there is a catch that this problem cannot be NP complete that easily (I forgot precise reasons since this was years past today).  

---

## 1 answers

### Answer by username_4 on 2015-04-08. Score: 1

Berlekamp, McEliece and Van Tilborg
[On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)]
proved that deciding if a binary code contains a code word of weight $w$ is NP-complete. In <http://statweb.stanford.edu/~cgates/PERSI/papers/85_04_radon.pdf>
Diaconis and Graham prove that deciding if a binary code of length $2m$ contains a code word of weight $n$ is NP-complete.

> **Comments:**
> **username_5**: Neither of those papers solves the OP's question. The first proof of the result that the OP is asking about was in Vardy's paper that Sasho links to in his comment above. It was a quite famous open question before then. The OP wants to know whether there is a simpler proof, which would necessarily have been discovered after Vardy's proof.  
> **username_5**: To expand my previous comment, there is a difference between asking whether there is a codeword of weight ***exactly*** *w*, and whether there is a non-zero codeword of weight ***at most*** *w*. For example, *is there a simple cycle of length exactly k?* is NP-hard, but there's a polynomial-time algorithm to find the shortest simple cycle in a graph.  

---

