# MPI-I-95-1-007

## 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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-95-1-007.pdf | 327 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: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-007

**BibTeX**
`@TECHREPORT{``RadhakrishnanSaluja95``,`

` 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},`

`}`