Technical Report CS0786

Several alternative formulations of the concept of an efficient proof system are nowadays coexisting in our field. These systems include the classical formulation of {\Cal NP}, interactive proof systems (giving rise to the class {\Cal IP}, computationally-sound proof systems, and probabilistically checkable proofs ({\Cal PCP}) which are closely related to multi-prover interactive proofs ({\Cal MIP}). Although these notions are sometimes introduced using the same generic phrases, they are actually very different in motivation, applications and expressive power. The main objective of this essay is to try to clarify these differences.