Proof verification and the hardness of approximation problems

TLDR

Our result builds on Arora and Safra’s 1998 verifier that reads a slowly growing number of proof bits, and it applies to the MAX SNP class—defined by Papadimitriou and Yannakakis—which includes hard problems such as vertex cover, maximum satisfiability, maximum cut, metric TSP, Steiner trees, and shortest superstring. We aim to show that every NP language admits a probabilistic verifier that uses only logarithmic random bits and reads a constant number of proof bits. The verifier operates by sampling a logarithmic number of random bits and examining a fixed-size fragment of the proof to decide membership. The verifier accepts all true instances with certainty and rejects false ones with probability at least ½, implying that unless NP=P, no MAX SNP‑hard problem admits a PTAS and that approximating maximum clique within a factor N^ε is NP‑hard for some ε>0.

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 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 N -vertex graph to within a factor of N ε is NP-hard.