5
$\begingroup$

A subspace $C$ of $\mathbb{F}_2^n$ is given for some $n \geq 1$. The space $C$ is given by its basis.

Is there a polynomial time algorithm to find the (nonzero) vector in $C$ of lowest hamming weight?

Motivation: Finding the distance of a given linear code.

1 Answers 1

3

For the purposes of this problem, we restrict ourselves to linear codes presented in terms of its generator (or equivalently, the parity check) matrix. Then Alexander Vardy (1997) showed that computing the minimum distance of a linear code exactly is NP-hard. [The decision version of this problem is: given a linear code $C$ and a bound $k$, does there exist a nonzero codeword $c$ in $C$ of weight $k$ or less? This version is NP-complete.]

There have been several improvements to this basic result -- it's now known that it's also quite hard to (a.) approximate the distance, (b.) decode a received word under the promise that there is a unique codeword close to it, etc. Unfortunately, I don't quite have the time right now to detail all the known developments, but this seems to be a good place to start: http://cseweb.ucsd.edu/~daniele/Research/CodeComp.html . I will try to expand this answer later.

Reference:

A. Vardy, The Intractability of Computing the Minimum Distance of a Code - IEEE Transactions on Information Theory, 1997.

  • 0
    I posted this answer on the OP's request. In the mean time, if someone else has a better, more detailed answer, I request them to post it -- I will delete my answer then.2011-11-28
  • 0
    Please don't delete the answer unless your reference is _also_ included in said "better, more detailed answer".2011-11-28
  • 0
    +1. Vardy's result came to mind for me, too. I would need to check (algorithmic complexity is a very weak area for me), but IIRC the NP-hard problem is to decide whether a linear code with a given generator matrix has a word of a weight below a given bound or not.2011-11-28
  • 0
    @Jyrki, Yes, if my understanding is right, the input is a generator matrix defining a code and the problem is to find the smallest weight of a nonzero word. I am stating it this way because I prefer to think in terms of the optimisation version; you describe the decision version accurately.2011-11-28
  • 0
    @Jyrki I have stated the result a bit more precisely. Thanks.2011-11-28
  • 0
    @Srivatsan Thanks for filling us all in, and for fixing my error! For some reason I always confuse the NP-hard and NP-complete versions :-)2011-11-30