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 language||English (US)|
|Number of pages||18|
|State||Published - Dec 1 2003|
All Science Journal Classification (ASJC) codes