Several alternative formulations of the concept of an efficient proof system
are nowadays coexisting in Theoretical Computer Science.
These systems include the classical
formulation of **NP**, *interactive proof systems*
(giving rise to the class **IP**),
*computationally-sound proof systems*,
and *probabilistically checkable proofs* (**PCP**)
which are closely related to
*multi-prover interactive proofs* (**MIP**).
Although these notions are sometimes introduced using the same
generic phrases, they are actually very different in motivation,
applications and expressive power.

Except for **NP**, all proof systems reviewed are probabilistic
and furthermore have a non-zero error probability. However, the error
probability is explicitly bounded and can be reduced by successive
applications of the proof system. In all cases, non-zero error probability
is essential to the interesting properties and consequences which these
probabilistic proof systems have.

- Probabilistic
Proof Systems - A Primer, June 2008.

This is the latest and most recommended exposition. It provides a comprehensive treatment of the basic notions and results, and contains proof outlines and/or sketches for the main results.

(This text is an abbreviated and self-contained version of Chapter 9 in Computational Complexity: A Conceptual Perspective.) -
Probabilistic Proof Systems (survey), May 1995.
(revised,
Dec. 1996).

This survey was intended for a general audience and has appeared in the proceedings of*ICM94*, the International Congress of Mathematicians 1994. It focuses on the very basics and presents some well-known constructions. -
A Taxonomy of Proof Systems, Dec. 1995 (revised Sept. 1996).

This survey was intended for readers with some background in computational complexity and appeared in the*Complexity Theory Retrospective II*. It provides a wider coverage than the first, but presents no constructions. -
Probabilistic Proof Systems (Lecture Notes), Sept. 1996.

These are lecture**notes**in the strict sense of the word. They were prepared for a series of lectures given in the Theory Student Seminar of the CS Department of UC-Berkeley.

- S. Vadhan, Lecture notes on Probabilistic Proof Systems - Part I (interactive and zero-knowledge proofs).
- M. Sudan, Lecture notes on Probabilistic Proof Systems - Part II (probabilistically checkable proofs).
- O. Goldreich, webpage on zero-knowledge (including a tutorial).
- O. Goldreich, papers on Probabilistic Proof Systems.

- Chapter 2 in Modern Cryptography, Probabilistic Proofs and Pseudorandomness surveys various types of probabilistic proof systems.
- Chapter 9 in Computational Complexity: A Conceptual Perspective (2008) provides a revised and extended version of the above.
- Chapter 4 in Foundations of Cryptography provides an extensive treatment of zero-knowledge.

Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers