Published May 1978
| Published
Journal Article
Open
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.
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.Attached Files
Published - BERieeetit78.pdf
Files
BERieeetit78.pdf
Files
(595.7 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:1bb5386e08a5b3ee4cb9ba90233315dd
|
595.7 kB | Preview Download |
Additional details
- Eprint ID
- 5607
- Resolver ID
- CaltechAUTHORS:BERieeetit78
- NASA/JPL/Caltech
- NAS 7-100
- Created
-
2006-10-25Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field