If a problem is shown to be NP-hard, then this gives us very strong evidence that no polynomial-time algorithm will ever solve the problem for all instances. There are many important problems in coding theory for which it is of interest to know whether we can solve them efficiently. For example: maximum likelihood decoding and finding the minimum distance of an arbitrary code. The non-existence of an efficient solver for these problems would imply that many other interesting problems in coding theory also cannot be solved efficiently. Further, while NP-hardness of a problem is not sufficient for cryptography, it is often used as a way to develop confidence that a problem will also be hard for cryptographic purposes.

In [1] and [2], it was shown that the above mentioned problems are NP-hard. The hardness of many related problems were also considered in [2] and [3]. The task of the student would be to summarize these NP-hardness results, understand which problems are known to be difficult and which ones are not and the implications of these results for coding theory and other fields.

[1] E. Berlekamp, R. McEliece, and H. van Tilborg, ‘On the inherent intractability of certain coding problems (Corresp.)’, IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 384–386, May 1978, doi: 10.1109/TIT.1978.1055873.
[2] A. Vardy, ‘The intractability of computing the minimum distance of a code’, IEEE Transactions on Information Theory, vol. 43, no. 6, pp. 1757–1766, Nov. 1997, doi: 10.1109/18.641542.
[3] M. Finiasz, ‘NP-completeness of Certain Sub-classes of the Syndrome Decoding Problem’, arXiv:0912.0453 [cs], Dec. 2009. Available: http://arxiv.org/abs/0912.0453

- Channel coding
- Some acquaintance with complexity theory (specifically the notion of NP-completeness) is preferable but not mandatory