On the Inherent Intractability of Certain Coding Problems: COSET WEIGHTS (Decoding a Binary Linear Code) and SUBSPACE WEIGHTS (a Codeword of Given Weight) Are NP-CompleteResearch Paper
A binary linear code is used on a noisy channel by transmitting codewords and correcting the errors at the receiver. If is a parity-check matrix of the code and is the received word, the receiver computes the syndrome and must find a minimum-weight error pattern with . A second basic question is whether a code has a codeword of a given…