 Main
Hamming Approximation of NP Witnesses
Published Web Location
https://doi.org/10.4086/toc.2013.v009a022Abstract
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 != NP, then every NPcomplete language has a verifier for which there is no (n/2n^(2/3+d))Hammingapproximation algorithm, for various constants d > 0. Our main result is that, if P != 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/2Hammingapproximation algorithms, but, if P != NP, have no (n/2n^epsilon)Hammingapproximation algorithms for any constant epsilon > 0. We show similar results for randomized algorithms.
Many UCauthored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
Enter the password to open this PDF file:













