On the inherent intractability of certain coding problems (Corresp.)
Elwyn R. Berlekamp, Robert J. McEliece, Henk van Tilborg · IEEE Transactions on Information Theory · 1978
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. This strongly suggests, but does not rigorously imply, that no algorithm for either of these problems which runs in polynomial time exists.