期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that the minimum distance of a linear code (or
equivalently, the weight of the lightest codeword) is
not approximable to within any constant factor in random polynomial
time (RP), unless NP equals RP.
Under the stronger assumption that NP is not contained in RQP
(random quasi-polynomial time),
we show that the minimum distance is not approximable to
within the factor 2log(1−)n, for any
0, where n denotes the block length of the code.
We also show that the minimum distance is not approximable
to within an additive error that is linear in the block
length of the code, unless NP equals RP.
Our results hold for codes over every finite field, including
the special case of binary codes. In the process we show that
the nearest codeword problem is hard to solve even under the
promise that the number of errors is (a constant factor) smaller
than the distance of the code (even if the code is asymptotically good).
This is a particularly meaningful version of the nearest codeword
problem.
