6
$\begingroup$

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?)

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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 ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542 ? $\endgroup$ – Sasho Nikolov Apr 8 '15 at 18:09
  • $\begingroup$ @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 $\endgroup$ – Anirbit Apr 8 '15 at 18:33
  • 3
    $\begingroup$ 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. $\endgroup$ – D.W. Apr 9 '15 at 20:59
  • $\begingroup$ 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! $\endgroup$ – Anirbit Apr 9 '15 at 22:15
  • 1
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov May 12 '15 at 8:08
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Shor Apr 8 '15 at 21:13
  • 6
    $\begingroup$ 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. $\endgroup$ – Peter Shor Apr 8 '15 at 21:15

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.