The intractability of computing the minimum distance of a code
Author:
- 1 November 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 43 (6) , 1757-1766
Abstract
It is shown 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 result constitutes a proof of the conjecture of Berlekamp, McEliece, and van Tilborg (1978). Extensions and applications of this result to other problems in coding theory are discussed.Keywords
This publication has 19 references indexed in Scilit:
- MDS array codes with independent parity symbolsIEEE Transactions on Information Theory, 1996
- Fixed-Parameter Tractability and Completeness I: Basic ResultsSIAM Journal on Computing, 1995
- Fixed-parameter tractability and completeness II: On completeness for W[1]Theoretical Computer Science, 1995
- A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rateIEEE Transactions on Information Theory, 1993
- Algebraic-Geometric Codes1991
- Bounds on the dimension of codes and subcodes with prescribed contraction indexLinear Algebra and its Applications, 1990
- The hardness of decoding linear codes with preprocessingIEEE Transactions on Information Theory, 1990
- New algorithms for finding irreducible polynomials over finite fieldsMathematics of Computation, 1990
- A construction of non-Reed-Solomon type MDS codesIEEE Transactions on Information Theory, 1989
- The Radon transform on Z2kPacific Journal of Mathematics, 1985