Citation
Abstract
In this article we will show that the problem of computing the minimum distance of an arbitrary binarv linear code is NP complete. This strongly suggests, but does not imply, that it is impossible to design a computer algorithm for computing the minimum distance of an arbitrary code whose running time is bounded by a polynomial in the number of inputs. distance d,,, ;,,- Here Qin = Minid Ax y)i x, ve x Fy} mit minimum nonzero weight of the code Wirin’
Details
- Volume
- 42-37
- Published
- February 15, 1977
- Pages
- 83–87
- File Size
- 326.7 KB