文章基本信息

标题：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.