de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Interactive Proof Systems

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45339

Saluja,  Sanjeev
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-95-1-007.pdf
(Any fulltext), 801KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Radhakrishnan, J., & Saluja, S.(1995). Interactive Proof Systems (MPI-I-1995-1-007). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A75C-E
Abstract
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.