Technical Report CS0786

TR#:CS0786
Class:CS
Title: A TAXONOMY OF PROOF SYSTEMS.
Authors: O. Goldreich
PDFCS0786.pdf
Abstract:

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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1993/CS/CS0786), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion
admin