Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-006 | 24th January 1996 00:00

Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept



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.

ISSN 1433-8092 | Imprint