LCS Publication Details
Publication Title: CS PROOFS
Publication Author: Micali, Silvio
Additional Authors:
LCS Document Number: MIT-LCS-TM-510
Publication Date: 6-1-1994
LCS Group: Theory of Computation
Additional URL: No URL Given
This paper puts forward a computationally-based notion of proof and explores it's implications to computation at large. In particular, given a random oracle or a suitable cryptographic assumption, we show that every computation possesses a short certificate vouching its correctness, and that under a cryptographic assumption, any program for a NP-complete problem is checkable in polynomial time.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.