- INSTANCE:
Linear binary code
*C*of length*n*and a string*x*of length*n*. - SOLUTION:
A codeword
*y*of*C*. - MEASURE:
The Hamming distance between
*x*and*y*, i.e.,*d(x,y)*.

*Bad News:*Not in APX [35].*Comment:*Not approximable within for any unless NPQP [35]. The complementary maximization problem, where the number of bits that agree between*x*and*y*is to be maximized, does not admit a PTAS [399].