Revised: April 24, 2013

Published: August 4, 2013

**Keywords:**complexity theory, inapproximability, approximation algorithms, Hamming distance

**Categories:**complexity theory, lower bounds, inapproximability, approximation algorithms, Hamming distance

**ACM Classification:**F.1.3

**AMS Classification:**68Q17

**Abstract:**
[Plain Text Version]

*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 language has 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.