Editing Interactive proof system (section)

=== PCP ===
{{main|Probabilistically checkable proof}}
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. {{tmath|1=\mathsf{PCP}(0,\mathsf{poly})}}, the class of polynomial-time machines with no randomness but access to a certificate,  is just '''NP'''. {{tmath|1=\mathsf{PCP}(\mathsf{poly},0)}}, the class of polynomial-time machines with access to polynomially many random bits is '''co-[[RP (complexity)|RP]]'''. Arora and Safra's first major result was that {{tmath|1= \mathsf{PCP}(\log, \log) = \mathsf{NP} }}; put another way, if the verifier in the '''NP''' protocol is constrained to choose only {{tmath|O(\log n)}} bits of the proof certificate to look at, this won't make any difference as long as it has {{tmath|O(\log n)}} random bits to use.<ref>Sanjeev Arora and [[Shmuel Safra]]. [http://citeseer.ist.psu.edu/arora92probabilistic.html Probabilistic Checking of Proofs: A New Characterization of NP]. ''Journal of the ACM'', volume 45, issue 1, pp. 70–122. January 1998.</ref>

Furthermore, the [[PCP theorem]] asserts that the number of proof accesses can be brought all the way down to a constant. That is, {{tmath|1=\mathsf{NP} = \mathsf{PCP}(\log, O(1))}}.<ref>Sanjeev Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. [http://citeseer.ist.psu.edu/376426.html Proof Verification and the Hardness of Approximation Problems]. Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 13–22. 1992.</ref> They used this valuable characterization of '''NP''' to prove that [[approximation algorithm]]s 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]].