Berlekamp, Elwyn R. and McEliece, Robert J. and van Tilborg, Henk C. A. (1978) On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24 (3). pp. 384-386. ISSN 0018-9448. doi:10.1109/TIT.1978.1055873. https://resolver.caltech.edu/CaltechAUTHORS:BERieeetit78
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 595kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:BERieeetit78
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.
| Item Type: | Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||
| Additional Information: | © 1978 IEEE. Reprinted with permission. Manuscript received March 2, 1977; revised September 14, 1977. The contribution of McEliece and van Tilborg to this correspondence represents one phase of research sponsored by the National Aeronautics and Space Administration under Contract No. NAS7-100, carried out at the Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA. We wish to thank one of the referees for pointing out to us the relation between the "weight ≤ w" decision problem and the minimum weight problem for linear codes. | ||||||||||||
| Funders: |
| ||||||||||||
| Issue or Number: | 3 | ||||||||||||
| DOI: | 10.1109/TIT.1978.1055873 | ||||||||||||
| Record Number: | CaltechAUTHORS:BERieeetit78 | ||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:BERieeetit78 | ||||||||||||
| Official Citation: | E. Berlekamp, R. McEliece and H. van Tilborg, "On the inherent intractability of certain coding problems (Corresp.)," in IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 384-386, May 1978. | ||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
| ID Code: | 5607 | ||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||
| Deposited By: | Archive Administrator | ||||||||||||
| Deposited On: | 25 Oct 2006 | ||||||||||||
| Last Modified: | 08 Nov 2021 20:27 |
Repository Staff Only: item control page
