Interactive Proof System - PCP

While the designers of IP considered generalizations of Babai's interactive proof systems, others considered restrictions. A very useful interactive proof system is PCP(f(n), g(n)), which is a restriction of MA where Arthur can only use f(n) random bits and can only examine g(n) bits of the proof certificate sent by Merlin (essentially using random access).

There are a number of easy-to-prove results about various PCP classes. PCP(0,poly), the class of polynomial-time machines with no randomness but access to a certificate, is just NP. PCP(poly,0), the class of polynomial-time machines with access to polynomially many random bits is co-RP. Arora and Safra's first major result was that PCP(log, log) = NP; put another way, if the verifier in the NP protocol is constrained to choose only O(log n) bits of the proof certificate to look at, this won't make any difference as long as it has O(log n) random bits to use.

Furthermore, the PCP theorem asserts that the number of proof accesses can be brought all the way down to a constant. That is, NP = PCP(log, O(1)). They used this valuable characterization of NP to prove that approximation algorithms do not exist for the optimization versions of certain NP-complete problems unless P = NP. Such problems are now studied in the field known as hardness of approximation.