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:

See also slides for a talk, 2021.

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