A Note on Time-Space Bounded Interactive Protocols.
In this paper, we examine the power of time-space bounded interactive protocols with private coins. The class of languages having logspace, polynomial-time bounded private coin protocols is exactly PSPACE. We generalize this result to other time-space bounded protocols. As a consequence we obtasin that EXPSPACE is exactly the class of languages having polynomial-space, exponential-time bounded private coin interactive protocols. This coupled with earlier work by Condon, Fortnow and Lund gives us the following characterization of standard complexity classes in terms of time-space bounded interactive protocols.
computer science; technical report
Previously Published As