On the computational complexity of blind detection of binary linear codes
share
In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes C of a given dimension k, for which the sum of distances between the observations and the code is minimized. In the existing literature, it has been stated that, when C is the set of all linear codes of dimension k and the rank of the observation matrix is larger than k, the problem is NP-hard. We prove that, for the same choice of C, the detection problem can in fact be solved in polynomial time when the rank of the observation matrix is at most k. Moreover, we prove that, for the practically relevant case when the set C only contains a fixed number of candidate linear codes, the detection problem is NP-hard. Finally, we identify a number of interesting open questions related to the code detection problem.
READ FULL TEXT