1992/01/01 by Sanjeev Arora, Carsten Lund, R. Motwani +2 · 16 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Machine Learning and Algorithms
paper · doi:10.1109/sfcs.1992.267823
openalex publication_date 1992/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.>