About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1993
Conference paper
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.