Verifying Membership in NP-languages, or How to Avoid Reading Long Proofs

an A.B. thesis by Leonid Reyzin
Thesis supervisor: Michael O. Rabin
 
Abstract

In March of 1996, I did my senior thesis on Probabilistically Checkable Proofs (the complexity class known as PCP). There is no original result in that thesis, but it presents a decent exposition of some of the major results about PCP with relation to NP, focusing mainly on what had been accomplished up to 1992. The goal was to be clearer than the 5 or so somewhat inconsistent conference and journal papers that it is based on. If you don't know much about PCP and want to find out, this may provide a good introduction (but if you want to dig deeper, remember that much more has been done since 1992).