PDMI TUM State University St. Petersburg
Steklov Institute St. Petersburg Technische Universität München State University St. Petersburg

Joint Advanced Student School (JASS)

Course 1: Proofs and Computers


St. Petersburg - Sunday, April 2 through Wednesday, April 12, 2006

Johannes Mittmann

IP=PSPACE

Abstract

In [Sh92], Adi Shamir proved a complete characterization of the complexity class IP. He showed 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 within polynomial space. This paper gives a detailed description of the proof. Besides the original paper, it is based on [Pa94] and [SchPr98].



Florian Zuleger Presentation:
IP=PSPACE [PDF]
Paper:
IP=PSPACE [PDF]