neal young / Sheldon13Hamming

Theory of Computing 9(22):685702(2013)Given a satisfiable 3SAT 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 polynomialtime verifier for any NPcomplete language. A $d(n)$Hammingapproximation 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, then every NPcomplete language has a verifier for which there is no $(n/2n^{2/3+\delta})$Hammingapproximation algorithm, for various constants $\delta\ge 0$.
Our main result is that, if P$\ne$NP, then every paddable NPcomplete language has a verifier that admits no $(n/2+O(\sqrt{n\log n}))$Hammingapproximation algorithm. That is, one cannot get even half the bits right. We also consider natural verifiers for various wellknown NPcomplete problems. They do have $n/2$Hammingapproximation algorithms, but, if P$\ne$NP, have no $(n/2n^\epsilon)$Hammingapproximation algorithms for any constant $\epsilon>0$.
We show similar results for randomized algorithms.First draft circulated in 2003.
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.