Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
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

Created:
August 22, 2023
Modified:
October 23, 2023