Probabilistic Proof Systems
Expositions by Oded Goldreich
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.
Four expositions of mine are available on-line are:
Proof Systems - A Primer, June 2008.
This is the latest and most recommended
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.
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.
Additional related material available on-line
See also Chapters in Books
Back to Oded Goldreich's homepage
or to General list of Oded Goldreich's papers