TY - GEN

T1 - Proof verification and hardness of approximation problems

AU - Arora, Sanjeev

AU - Lund, Carsten

AU - Motwani, Rajeev

AU - Sudan, Madhu

AU - Szegedy, Mario

PY - 1992/1/1

Y1 - 1992/1/1

N2 - The class PCP(f(n),g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y such that the machine accepts for all random choices but if x not in L then for every oracle y the machine rejects with high probability. Arora and Safra (1992) characterized NP as PCP(log n, (loglogn)/sup O(1)/). The authors improve on their result by showing that NP=PCP(logn, 1). The result has the following consequences: (1) MAXSNP-hard problems (e.g. metric TSP, MAX-SAT, MAX-CUT) do not have polynomial time approximation schemes unless P=NP; and (2) for some epsilon >0 the size of the maximal clique in a graph cannot be approximated within a factor of n/sup epsilon / unless P=NP.

AB - The class PCP(f(n),g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y such that the machine accepts for all random choices but if x not in L then for every oracle y the machine rejects with high probability. Arora and Safra (1992) characterized NP as PCP(log n, (loglogn)/sup O(1)/). The authors improve on their result by showing that NP=PCP(logn, 1). The result has the following consequences: (1) MAXSNP-hard problems (e.g. metric TSP, MAX-SAT, MAX-CUT) do not have polynomial time approximation schemes unless P=NP; and (2) for some epsilon >0 the size of the maximal clique in a graph cannot be approximated within a factor of n/sup epsilon / unless P=NP.

UR - http://www.scopus.com/inward/record.url?scp=85028925878&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028925878&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1992.267823

DO - 10.1109/SFCS.1992.267823

M3 - Conference contribution

AN - SCOPUS:85028925878

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 14

EP - 23

BT - Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

PB - IEEE Computer Society

T2 - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

Y2 - 24 October 1992 through 27 October 1992

ER -