Volume 9 (2013) Article 22 pp. 685-702
Hamming Approximation of NP Witnesses
by
Received: August 13, 2012
Revised: April 24, 2013
Published: August 4, 2013
Download article from ToC site:
[PDF (293K)]    [PS (1036K)]    [PS.GZ (324K)]
[Source ZIP]
Keywords: complexity theory, 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.