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
N1 - Publisher Copyright:
© 1992 IEEE.
PY - 1992
Y1 - 1992
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 -