Probabilistic Proof Systems
Three Texts 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.
Material on-line
- 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 is to appear in 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.
