Proof verification and hardness of approximation problems
- 1 January 1992
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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.<>Keywords
This publication has 26 references indexed in Scilit:
- Approximating clique is almost NP-completePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the Approximation of Maximum SatisfiabilityJournal of Algorithms, 1994
- The Traveling Salesman Problem with Distances One and TwoMathematics of Operations Research, 1993
- IP = PSPACEJournal of the ACM, 1992
- On the complexity of approximating the independent set problemInformation and Computation, 1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) AlgorithmsIEEE Annals of the History of Computing, 1984
- P-Complete Approximation ProblemsJournal of the ACM, 1976
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971