Algorithmic complexity in coding theory and the minimum distance problem
Alexander Vardy · 1997
We start with an overview of algorithmiccomplexity problems in coding theory We then show that the problem of computing the minimum distance of a binary linear code is NP-hard, and the corresponding decision problem is NP-complete. This constitutes a proof of the conjecture Bedekamp, McEliece, van Tilborg, dating back to 1978. Extensions and applications of this result to other problems in coding theory are discussed.