Probabilistically checkable proof

From TheBestLinks.com

In computational complexity theory, PCP is the class of decision problems having probabilistically checkable proof systems.

A PCP system can be viewed as an interactive proof system in which the prover is a memoryless oracle (essentially a string) and the verifier is a polynomial-time randomized algorithm. For an input which belongs to the language (a YES-instance), there exists an oracle (or proof) for which the verifier accepts with certainty; for NO-instances, the verifier rejects with probability at least 1/2, whatever be the oracle (compare Co-RP).

Another way of looking at PCP is as a more powerful version of NP. For languages in NP, the time spent checking the proof is at least as long as the proof itself, while this need not be the case for languages in PCP. Thus much longer proofs are possible for PCP than for NP.

Observe that in the above, we have not set a bound on the number of oracle queries the verifier can make. Another factor that affects the power of the PCP system is the number of coin tosses the verifier can make: the more the randomness available, the more selectivity the verifier can exercise in examining the proof. Thus, PCP is actually a meta-class of complexity classes parametrized by two functions.

PCP(r(.), q(.)) is the class of languages having probabilistically checkable proofs in which the verifier can make r(n) coin tosses and q(n) oracle queries on an input of size n.

Simple special cases (poly denotes polynomial time, log denotes logarithmic time):

PCP (poly, 0) = Co-RP
PCP (0, poly) = NP

Notable facts:

PCP (poly, poly) = NEXP
If NP ⊂ PCP (o(log), o(log)) then NP = P
NP ⊃ PCP (log, poly)

The PCP Theorem, one of the crowning jewels of complexity theory, states: NP ⊂ PCP (log, O(1)). This is useful for proving impossibility results for approximation algorithms.

Reference

PCP lecture notes (http://www.cs.jhu.edu/~scheideler/courses/600.471_S03/lecture_8.pdf) - by Christian Scheideler
PCP notes and slides (http://theory.lcs.mit.edu/~madhu/pcp/course.html) - by Madhu Sudan

Important complexity classes