CJTCS Volume 2000 Article 2

Volume 2000

Article 2

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

Abstract

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).

Preformatted versions of the article
- DVI (74,684 bytes)
- PostScript (280,222 bytes)
- PDF (247,891 bytes)
- Audio by AsTeR (to appear)
Source materials for custom formatting
- LaTeX (cj00-02.tex, 54,481 bytes)
- BIBTeX (cj00-02.bib, 85,578 bytes)
- Parameter settings for custom formatting (cjropts.tex, 165 bytes)
- Self citation in BIBTeX (311 bytes)
Online discussion
Instructions for Readers

DOI: 10.4086/cjtcs.2000.002

Volume 2000, Article 2

Article 3

Volume 2000 [back]

Published articles