Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Interactive Proof Systems

Radhakrishnan, Jaikumar and Saluja, Sanjeev

MPI-I-95-1-007. March 1995, 121 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s): KBytes; 800 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Radhakrishnan, Jaikumar and Saluja, Sanjeev},
  TITLE = {Interactive Proof Systems},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-95-1-007},
  MONTH = {March},
  YEAR = {1995},
  ISSN = {0946-011X},