Abstract:
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.