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