期刊名称:Electronic Colloquium on Computational Complexity
印刷版ISSN:1433-8092
出版年度:1997
卷号:1997
出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要:We show that in the context of nonuniform complexity,
nondeterministic logarithmic space bounded computation can be made
unambiguous. An analogous result holds for the class of problems
reducible to context-free languages. In terms of complexity classes,
this can be stated as:
NL/poly = UL/poly
LogCFL/poly = UAuxPDA(log n, polynomial)/poly