Chicago Journal of Theoretical Computer Science

Volume 2000

Article 2

Published by MIT Press. Copyright 2000 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.

Characterizing Small Depth and Small Space Classes by Operators of Higher Types

Manindra Agrawal (Indian Institute of Technology, Kanpur, India), Eric Allender (Rutgers University), Samir Datta (Rutgers University), Heribert Vollmer (Universitat Wuerzburg, Wuerzburg, Germany), and Klaus W. Wagner (Universitat Wuerzburg, Wuerzburg, Germany)
6 August 2000

Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators quantifying over oracles. We obtain new characterizations of NC, L, NL, NP, and NSC (the nondeterministic version of SC). In some cases, we prove that our simulations are optimal (for instance, in bounding the number of queries to the oracle).

DOI: 10.4086/cjtcs.2000.002
[] Volume 2000, Article 2 [] Article 3
[back] Volume 2000 [back] Published articles
[CJCTS home]