Efficient probabilistically checkable proofs and applications to approximation

Abstract

We construct multi-prover proof systems for NP which use only a constant number of provers to simultaneously achieve low error, low randomness and low answer size. As a consequence, we obtain asymptotic improvements to approximation hardness results for a wide range of optimization problems including minimum set cover, dominating set, maximum clique, chromatic number, and quartic programming; and constant factor improvements on the hardness results for MAXSNP problems. In particular, we show that approximating minimum set cover within any constant is NP-complcte; approximating minimum set cover within clogn, for c < 1/8, implies NP ⊆ DTIME(nlog log n); approximating the maximum of a quartic program within any constant is NP-complete; approximating maximum clique or chromatic number within n1/29 implies NP ⊆ BPP; and approximating MAX-3SAT within 113/112 is NP-complete.