Interactive Proof Systems

The report is a compilation of lecture notes that were prepared during the course ``Interactive Proof Systems'' given by the authors at Tata Institute of Fundamental Research, Bombay. These notes were also used for a short course ``Interactive Proof Systems'' given by the second author at MPI, Saarbruecken. The objective of the course was to study the recent developments in complexity theory about interactive proof systems, which led to some surprising consequences on nonapproximability of NP hard problems. We start the course with an introduction to complexity theory and covered some classical results related with circuit complexity, randomizations and counting classes, notions which are either part of the definitions of interactive proof systems or are used in proving the above results. We define arthur merlin games and interactive proof systems, which are equivalent formulations of the notion of interactive proofs and show their equivalence to each other and to the complexity class PSPACE. We introduce probabilistically checkable proofs, which are special forms of interactive proofs and show through sequence of intermediate results that the class NP has probabilistically checkable proofs of very special form and very small complexity. Using this we conclude that several NP hard problems are not even weakly approximable in polynomial time unless P = NP