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

The PCP theorem, proven in the early 1990's, states that every NP problem has a very efficient probabilistically checkable proof system. This theorem has the following astonishing consequence: every proof for any mathematical statement can be formalized, so that one can check whether it is correct or not by only reading a constant number of letters from it! More precisely, one can choose which letters of the proof to look at using a certain random process, and then after reading them, one can declare the proof "correct" or "false". In this process a correct proof will always be declared as such, while any attempt to prove a wrong statement will be declared false with probability at least 1/2 (repeating this process several times can detect a false proof with arbitrarily high probability).

In complexity theory, 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