Proof veri¯cation and hardness of approximation problems

We show that every language in NP has a probablistic verier that checks mem-bership proofs for it using logarithmic number of random bits and 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 verier accepts with probability 1 (i.e., for every choice of its random string). For strings not in the language, the verier rejects every provided proof " with probability at least 1=2. Our result builds upon and improves a recent result of Arora and Safra [6] whose veriers examine a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length). As a consequence we prove that no MAX SNP-hard problem has a polynomial time approximation scheme, unless NP=P. The class MAX SNP was dened by Pa-padimitriou and Yannakakis [82] and hard problems for this class include vertex cover, maximum satisability, maximum cut, metric TSP, Steiner trees and shortest superstring. We also improve upon the clique hardness results of Feige, Goldwasser, Lovász, Safra and Szegedy [42], and Arora and Safra [6] and shows that there exists a positive such that approximating the maximum clique size in an N-vertex graph to within a factor of N is NP-hard.