[Sha90] IP = PSPACE

Authors: Adi Shamir | Venue: FOCS 1990 | Source

Abstract

In this paper, it is proven that when both randomization and interaction are allowed, the proofs that can be verified in polynomial time are exactly those proofs that can be generated with polynomial space.

BibTeX

Copy

@Inproceedings{FOCS:Shamir90,
  author = {Adi Shamir},
  title = {{IP}={PSPACE}},
  pages = {11--15},
  booktitle = {31st Annual Symposium on Foundations of Computer Science},
  address = {St. Louis, MO, USA},
  month = {oct~22--24},
  publisher = {{IEEE} Computer Society Press},
  year = {1990},
  doi = {10.1109/FSCS.1990.89519},
}