Journal of the ACM Bibliography

Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70-122, January 1998. [BibTeX entry]
Preliminary version

A preliminary version of these results was presented in: Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; a new characterization of NP. In 33rd Annual Symposium on Foundations of Computer Science, pages 2-13, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation; F.1.3 [Computation by Abstract Devices]: Complexity Classes; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic

General Terms: Algorithms, Theory, Verification

Additional Key Words and Phrases: Approximation algorithms, complexity hierarchies, computations on polynomials and finite fields, error-correcting codes, hardness of approximations, interactive computation, NP-completeness, probabilistic computation, proof checking, reducibility and completeness, trade-offs/relations among complexity measures

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database