期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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).
关键词：Complexity classes, Logarithmic time, NC, NSC, operators, SC
