On the inherent intractability of certain coding problems (Corresp.)
On the inherent intractability of certain coding problems (Corresp.)
E. Berlekamp,R. McEliece,H. V. Tilborg
1978 · DOI: 10.1109/TIT.1978.1055873
IEEE Transactions on Information Theory · 1,623 Citations
TLDR
The fact that the general decoding problem for linear codes and the general problem of finding the weights of a linear code are both NP-complete is shown strongly suggests, but does not rigorously imply, that no algorithm for either of these problems which runs in polynomial time exists.