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.