On the inherent intractability of certain coding problems

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

754 Citaten (Scopus)
7 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)384-386
Aantal pagina's3
TijdschriftIEEE Transactions on Information Theory
Volume24
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 1978

Vingerafdruk Duik in de onderzoeksthema's van 'On the inherent intractability of certain coding problems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit