首页    期刊浏览 2024年11月25日 星期一
登录注册

文章基本信息

  • 标题:Making Nondeterminism Unambiguous
  • 本地全文:下载
  • 作者:Klaus Reinhardt ; Eric Allender
  • 期刊名称: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
  • 关键词:LogCFL, NLOG, Nondeterministic space, ULOG, Unambiguous computation
国家哲学社会科学文献中心版权所有