### Proof verification and the hardness of approximation problemsProof verification and the hardness of approximation problems

Access Restriction
Subscribed

 Author Arora, Sanjeev ♦ Lund, Carsten ♦ Motwani, Rajeev ♦ Sudan, Madhu ♦ Szegedy, Mario Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1998 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword NP-completeness ♦ Optimization ♦ Proof verification ♦ Randomness Abstract We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a $\textit{constant}$ number of bits in the proof. If a string is in the language, then there exists a proof such that the verifier accepts 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 improves a recent result of Arora and Safra [1998] whose verifiers 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 defined by Papadimitriou and Yannakakis [1991] and hard problems for this class include vertex cover, maximum satisfiability, maximum cut, metric TSP, Steiner trees and shortest superstring. We also improve upon the clique hardness results of Feige et al. [1996] and Arora and Safra [1998] and show that there exists a positive ε such that approximating the maximum clique size in an $\textit{N}-vertex$ graph to within a factor of $\textit{N}ε$ is NP-hard. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1998-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 45 Issue Number 3 Page Count 55 Starting Page 501 Ending Page 555

#### Open content in new tab

Source: ACM Digital Library