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 $2^{\log^{(1 - \epsilon)} n}$, for any
$\epsilon > 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.

Our results strengthen (though using stronger assumptions) a
previous result of Vardy who showed that the minimum
distance is NP-hard to compute exactly. Our results are obtained
by adapting proofs of analogous results for integer lattices due to
Ajtai and Micciancio.
A critical component in the adaptation is our use of
linear codes that perform better than random (linear) codes.