Characterizing Small Depth and Small Space Classes by Operators of Higher Type.
Manindra Agrawal, Eric Allender, Samir K. Datta, Heribert Vollmer, Klaus W. Wagner · Chicago Journal of Theoretical Computer Science · 2000
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).