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

669 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

Decoding
coding
Polynomials
time

Cite this

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

}

On the inherent intractability of certain coding problems. / Berlekamp, E.R.; McEliece, R.J.; Tilborg, van, H.C.A.

In: IEEE Transactions on Information Theory, Vol. 24, No. 3, 1978, p. 384-386.

Research output: Contribution to journalArticleAcademicpeer-review

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 -