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

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 1 , 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). 1 Introduction Interactive proofs motivate complexity theorists to study new modes of computation. These modes have been studied to great effect in the setting of polynomial time (e.g. [Sha92, LFKN92, BFL90]) and small space-bounded classes (e.g. [FL93, CL95]). Is it possible to study interactive proofs in the context of even smaller complexity classes? Would such a study be useful or interesting? It has often proved very useful to study modes of computation on very small complexity classes, although it has not always been clear at first, just ..