On the inherent intractability of certain coding problems

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

doi:10.1109/TIT.1978.1055873

On the inherent intractability of certain coding problems

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

Discrete Mathematics

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer 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-2	Engels
Pagina's (van-tot)	384-386
Aantal pagina's	3
Tijdschrift	IEEE Transactions on Information Theory
Volume	24
Nummer van het tijdschrift	3
DOI's	https://doi.org/10.1109/TIT.1978.1055873
Status	Gepubliceerd - 1978

Toegang tot document

10.1109/TIT.1978.1055873

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

Citeer dit

@article{90ee9889a31f48fea3f81d9b1597ac03,

title = "On the inherent intractability of certain coding problems",

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.",

author = "E.R. Berlekamp and R.J. McEliece and {Tilborg, van}, H.C.A.",

year = "1978",

doi = "10.1109/TIT.1978.1055873",

language = "English",

volume = "24",

pages = "384--386",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers",

number = "3",

}

TY - JOUR

T1 - On the inherent intractability of certain coding problems

AU - Berlekamp, E.R.

AU - McEliece, R.J.

AU - Tilborg, van, H.C.A.

PY - 1978

Y1 - 1978

N2 - 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.

AB - 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.

U2 - 10.1109/TIT.1978.1055873

DO - 10.1109/TIT.1978.1055873

M3 - Article

VL - 24

SP - 384

EP - 386

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 3

ER -