On the complexity of some coding problems (Corresp.)
Simeon C. Ntafos, S. L. Hakimi · IEEE Transactions on Information Theory · 1981
It is shown that the problem of finding a codeword with least weight and whose weight is not a multiple ofkin a binary linear code belongs to the class of "nondeterministic polynomial (NP)-hard" problems for anyk\geq 2. Some other related problems are shown to belong to the same class. These results were motivated by a conjecture due to Berlekamp, McEliece, and van Tilborg that the problem of finding the Hamming distance of a code is NP-hard.