Hamming Approximation of NP Witnesses
Daniel Sheldon, Neal E. Young · eScholarship (California Digital Library) · 2012
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 P6=NP, every NP-complete language has a verifier for which there is no (n/2−n2/3+δ)-Hamming-approximation algorithm, for various constants δ ≥ 0. Our main result is that, if P6=NP, then every paddable NP-complete language has a verifier that admits no (n/2+O( n logn))-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 6=NP, have no (n/2−nε)-Hamming-approximation algorithms for any constant ε> 0. We show similar results for randomized algorithms. ∗Supported by NSF Award IIS-1125098. †Supported by NSF Award CCF-1117954.