Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-057 | 10th September 1998 00:00

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

RSS-Feed




TR98-057
Authors: Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
Publication: 12th September 1998 16:28
Downloads: 1298
Keywords: 


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 $\NCe$, $\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).



ISSN 1433-8092 | Imprint