Editing Probabilistically checkable proof (section)

== History and significance ==
The theory of probabilistically checkable proofs studies the power of probabilistically checkable proof systems under various restrictions of the parameters (completeness, soundness, randomness complexity, query complexity, and alphabet size).  It has applications to [[Computational complexity theory|computational complexity]] (in particular [[hardness of approximation]]) and [[cryptography]].

The definition of a probabilistically checkable proof was explicitly introduced by Arora and Safra in 1992,{{r|as92}} although their properties were studied earlier.  In 1990 Babai, Fortnow, and Lund proved that '''PCP'''[poly(''n''), poly(''n'')] = '''[[NEXP]]''', providing the first nontrivial equivalence between standard proofs ('''NEXP''') and probabilistically checkable proofs.{{r|bfl90}}  The [[PCP theorem]] proved in 1992 states that {{math|1={{sans-serif|PCP}}[''O''(log ''n''),''O''(1)] = {{sans-serif|NP}}}}.{{r|as92|almss}}

The theory of [[hardness of approximation]] requires a detailed understanding of the role of completeness, soundness, alphabet size, and query complexity in probabilistically checkable proofs.