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/or significance:
“I believe that history has shape, order, and meaning; that exceptional men, as much as economic forces, produce change; and that passé abstractions like beauty, nobility, and greatness have a shifting but continuing validity.”
—Camille Paglia (b. 1947)
“For a parent, it’s hard to recognize the significance of your work when you’re immersed in the mundane details. Few of us, as we run the bath water or spread the peanut butter on the bread, proclaim proudly, “I’m making my contribution to the future of the planet.” But with the exception of global hunger, few jobs in the world of paychecks and promotions compare in significance to the job of parent.”
—Joyce Maynard (20th century)