The PCP theorem [after Arora, Lund, Motwani, Safra, Sudan, Szegedy]

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

A new characterization of the complexity class NP in terms of probabilistically checkable proofs has had unexpected consequences in combinatorial optimization. The PCP theorem formalizes the idea that statements with short proofs can be checked with a constant number of random probes. This implies that many NP complete problems (such as coloring a graph) cannot be solved approximately with any reasonable level of accuracy.

Original languageEnglish (US)
Pages (from-to)19-36
Number of pages18
JournalAsterisque
Issue number290
StatePublished - Dec 1 2003

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The PCP theorem [after Arora, Lund, Motwani, Safra, Sudan, Szegedy]'. Together they form a unique fingerprint.

Cite this