DocumentCode
2357599
Title
CS proofs
Author
Micali, Silvio
Author_Institution
Lab. for Comput. Sci., MIT, Cambridge, MA, USA
fYear
1994
fDate
20-22 Nov 1994
Firstpage
436
Lastpage
453
Abstract
This paper puts forward a computationally-based notion of proof and explores its 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 𝒩𝒫-complete problem is checkable in polynomial time. In addition, our work provides the beginnings of a theory of computational complexity that is based on “individual inputs” rather than languages
Keywords
computational complexity; cryptography; CS proofs; NP complete problem; computational complexity; computationally sound proof; computationally-based notion; cryptographic assumption; polynomial time; proof; random oracle; Complexity theory; Computational complexity; Computer science; Cryptography; Laboratories; NP-complete problem; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Conference_Location
Santa Fe, NM
Print_ISBN
0-8186-6580-7
Type
conf
DOI
10.1109/SFCS.1994.365746
Filename
365746
Link To Document