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

文章基本信息

  • 标题:Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept
  • 本地全文:下载
  • 作者:Bernd Borchert, Antoni Lozano
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:1996
  • 卷号:1996
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:This note connects two topics of Complexity Theory: The topic of succinct circuit representations initiated by Galperin and Wigderson and the topic of leaf languages initiated by Bovet, Crescenzi, and Silvestri. It will be shown for any language that its succinct version is polynomial-time many-one complete for the leaf language class determined by it. Furthermore it will be shown that if one uses for the succinct version formulas or branching programs instead of circuits then one will get complete problems for ALOGTIME leaf language classes and logspace leaf language classes, respectively.
国家哲学社会科学文献中心版权所有