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 (in particular hardness of approximation) and cryptography.
The definition of a probabilistically checkable proof was explicitly introduced by Arora and Safra in 1992, although their properties were studied earlier. In 1990 Babai, Fortnow, and Lund proved that PCP = NEXP, providing the first nontrivial equivalence between standard proofs (NEXP) and probabilistically checkable proofs. The PCP theorem proved in 1992 states that PCP = NP.
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.
Read more about this topic: Probabilistically Checkable Proof
Famous quotes containing the words history and, history and/or significance:
“There is a constant in the average American imagination and taste, for which the past must be preserved and celebrated in full-scale authentic copy; a philosophy of immortality as duplication. It dominates the relation with the self, with the past, not infrequently with the present, always with History and, even, with the European tradition.”
—Umberto Eco (b. 1932)
“The only thing worse than a liar is a liar that’s also a hypocrite!
There are only two great currents in the history of mankind: the baseness which makes conservatives and the envy which makes revolutionaries.”
—Edmond De Goncourt (1822–1896)
“The hysterical find too much significance in things. The depressed find too little.”
—Mason Cooley (b. 1927)