Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. A Note on Time-Space Bounded Interactive Protocols.

A Note on Time-Space Bounded Interactive Protocols.

File(s)
91-1198.ps (240.71 KB)
91-1198.pdf (1.06 MB)
Permanent Link(s)
https://hdl.handle.net/1813/7038
Collections
Computer Science Technical Reports
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
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1198
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance