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