CS proofs

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 /spl Nscr//spl Pscr/-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.>