• Theory of Computing 9(22):685-702(2013)

  With Daniel Sheldon
  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, then 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 cannot 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.

  First draft circulated in 2003.

  • more...
  •   full text
    
  •   bibtex
    
  •   google scholar
    
  •   doi
    

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.