NEAREST CODEWORD

• 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 $2^{\log^{1-\varepsilon } n}$ for any $\varepsilon >0$ unless NP$\subset$QP [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].