Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7038
Title: A Note on Time-Space Bounded Interactive Protocols.
Authors: Rohatgi, Pankaj
Keywords: computer science
technical report
Issue Date: Apr-1991
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1198
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.
URI: http://hdl.handle.net/1813/7038
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
91-1198.pdf1.09 MBAdobe PDFView/Open
91-1198.ps240.71 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us