### 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 |

Publisher | IEEE Computer Society |

Pages | 14-23 |

Number of pages | 10 |

ISBN (Electronic) | 0818629002 |

DOIs | |

State | Published - Jan 1 1992 |

Externally published | Yes |

Event | 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States Duration: Oct 24 1992 → Oct 27 1992 |

### Publication series

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

Volume | 1992-October |

ISSN (Print) | 0272-5428 |

### Conference

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

Country | United States |

City | Pittsburgh |

Period | 10/24/92 → 10/27/92 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

## Fingerprint Dive into the research topics of 'Proof verification and hardness of approximation problems'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992*(pp. 14-23). [267823] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 1992-October). IEEE Computer Society. https://doi.org/10.1109/SFCS.1992.267823