DocumentCode :
933925
Title :
On the complexity of some coding problems (Corresp.)
Author :
Ntafos, S.C. ; Hakimi, S.L.
Volume :
27
Issue :
6
fYear :
1981
fDate :
11/1/1981 12:00:00 AM
Firstpage :
794
Lastpage :
796
Abstract :
It is shown that the problem of finding a codeword with least weight and whose weight is not a multiple of 
in a binary linear code belongs to the class of "nondeterministic polynomial (NP)-hard" problems for any 
. 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.
in a binary linear code belongs to the class of "nondeterministic polynomial (NP)-hard" problems for any . 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.Keywords :
Linear codes; Bridges; Error correction codes; Hamming distance; Linear code; NP-complete problem; Null space; Parity check codes; Polynomials; Vectors; Welding;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1981.1056419
Filename :
1056419
Link To Document :
