PROOF VERIFICATION AND THE HARDNESS OF APPROXIMATION-PROBLEMS

We show that every language in NP has a probablistic verifier that che cks membership proofs for it using logarithmic number of random bits a nd by examining a constant number of bits in the proof. If a string is in the language, then there exists a proof such that the verifier acc epts with probability 1 (i.e., for every choice of its random string). For strings not in the language, the verifier rejects every provided ''proof'' with probability at least 1/2. Our result builds upon and im proves a recent result of Arora and Safra [1998] whose verifiers exami ne a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length). As a consequence, w e prove that no MAX SNP-hard problem has a polynomial time approximati on scheme, unless NP = P. The class MAX SNP was defined by Papadimitri ou and Yannakakis [1991] and hard problems for this class include vert ex cover, maximum satisfiability, maximum cut, metric TSP, Steiner tre es and shortest superstring. We also improve upon the clique hardness results of Feige et al. [1996] and Arora and Safra [1998] and show tha t there exists a positive epsilon such that approximating the maximum clique size in an N-vertex graph to within a factor of N-epsilon is NP -hard.