PCP Theorem and Hardness of Computing Approximate

Since we have few techniques for proving strong lowerbounds on Turing machine computations, an interim approach is to study interrelationships between various complexity questions. We usually prove interrelationships using reductions. Examples of such efforts include (in addition to the ones studied in the next three lectures) the following. (1) Most of cryptography, like message authentication, digital signatures, pseudorandom generation, etc. is based on reductions. (2) Papadimitriou’s complexity class based on non-constructive math proofs [Pap94]. (3) Sahai-Vadhan’s complete problems for zero-knowledge [SV97]. (4) Levin’s theory of average case complexity [Lev]. (5) Fixed parameter tractability theory introduced by Downey and Fellows [DF95]. The next three lectures show this reduction-based methodology in action for three important issues. We note that there are many examples of complexity classes for which the reduction-based effort has not proved as successful, such as BPP, NP � coNP, and quantum classes. There are inherent obstacles in proving that these classes have complete problems [Pap94b]