A Note on Time-Space Bounded Interactive Protocols.
Collections
Author
Rohatgi, Pankaj
Abstract
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.
Date Issued
1991-04
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1198
Type
technical report