文章基本信息

标题：Characterizing Small Depth and Small Space Classes by Operators of Higher Types
本地全文：下载
作者：Manindra Agrawal ; Eric Allender ; Samir Datta 等
期刊名称：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