期刊名称: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.