2
$\begingroup$

Suppose that $F_2$ denotes the field with $2$ elements. We are given $m$ vectors $\{x_1, \ldots, x_m\}$ in $F_2^d$ which are a basis for a subspace $W$.

Suppose we have a vector $v \in F_q^m$, and we want to find a $w \in W$ that is closest to $v$ in the Hamming metric.

What is the complexity of this problem, as a function of $md$?

1) It's clear that there is an algorithm taking exponentially many steps. $W$ has $2^m$ elements, each of which takes $d$ bits to describe. So we just search through them.

2) It's unclear to me if this problem is even in $NP$. I can verify in polynomial time whether one vector in $W$ is closer to $v$ than another vector in $W$, but I do not know how to verify if one is the closest (or minimizes the distance). I suspect that it is impossible to do. Can anyone outline or refer me to a proof that this problem is not in $NP$?

3) If it is in $NP$, then is it $NP$-hard?

I guess this is well known, and presumably already discussed on this webpage. I poked around for a bit and couldn't find it, however. A reference would be welcome.

$\endgroup$
3
$\begingroup$

Your problem is known as the nearest codeword problem, and it is NP-hard to approximate. See for example lecture notes of Madhu Sudan. The way to make this problem an NP-problem is to ask whether the distance is at most a given distance. Regarding algorithms, I suggest taking a look at a paper of Alon, Panigrahy and Yekhanin, Deterministic Approximation Algorithms for the Nearest Codeword Problem.

$\endgroup$

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.