NASA NTRS · 19780054314
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.
Keep this discovery
Explore connections, maps & timelines
Berlekamp, E. R., Mceliece, R. J., Van Tilborg, H. C. A.. 1978-05-01. On the inherent intractability of certain coding problems. https://ntrs.nasa.gov/citations/19780054314
Cite the original work for its findings. Save a collection to share your selection of sources.