On the inherent intractability of certain coding problems

E.R. Berlekamp, R.J. McEliece, H.C.A. Tilborg, van

Research output: Contribution to journalArticleAcademicpeer-review

747 Citations (Scopus)
7 Downloads (Pure)

Abstract

The fact that the general decoding problem for linear codes and the general problem of finding the weights of a linear code are both NP-complete is shown. This strongly suggests, but does not rigorously imply, that no algorithm for either of these problems which runs in polynomial time exists.
Original languageEnglish
Pages (from-to)384-386
Number of pages3
JournalIEEE Transactions on Information Theory
Volume24
Issue number3
DOIs
Publication statusPublished - 1978

Fingerprint Dive into the research topics of 'On the inherent intractability of certain coding problems'. Together they form a unique fingerprint.

Cite this