Theory of Computing
-------------------
Title     : Hamming Approximation of NP Witnesses
Authors   : Daniel Sheldon and Neal E. Young
Volume    : 9
Number    : 22
Pages     : 685-702
URL       : https://theoryofcomputing.org/articles/v009a022

Abstract
--------

Given a satisfiable 3-SAT formula, how hard is it to find an assignment to 
the variables that has Hamming distance at most $n/2$ to a satisfying 
assignment?  More generally, consider any polynomial-time verifier for any 
NP-complete language. A _d(n)-Hamming-approximation algorithm_ for the 
verifier is one that, given any member $x$ of the language, outputs in 
polynomial time a string $a$ with Hamming distance at most d(n) to some
witness $w$, where $(x,w)$ is accepted by the verifier. Previous results 
have shown that, if P \ne NP, every NP -complete language has a verifier 
for which there is no $(n/2-n^{2/3+\delta})$-Hamming-approximation algorithm, 
for various constants $\delta\ge 0$.

Our main result is that, if  P \ne NP, then every paddable NP-complete languagehas a verifier that admits no $(n/2+O(\sqrt{n\log n}))$-Hamming-approximation 
algorithm. That is, one can't get even _half_ the bits right. We also consider
_natural_ verifiers for various well-known  NP -complete problems. They do 
have $n/2$-Hamming-approximation algorithms, but, if P \ne NP, have no 
$(n/2-n^\epsilon)$-Hamming-approximation algorithms for any constant 
$\epsilon>0$.

We show similar results for randomized algorithms.