期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper, we present stronger results in the theory of succinct
problem representation by boolean circuits, and establish a close
relationship between succinct problems and leaf languages. As
a major tool, we use quantifierfree projection reductions
from descriptive complexity theory.
In particular, we show that the succinct upgrading technique
can be improved to completeness under monotone projection
reductions. Moreover, we show that for each problem A the
succinct problem sA is complete for the leaf language leaf(A) under
monotone projection reductions. Thus, we obtain a precise
characterization of the complexity gap obtained by succinct
representation. Furthermore, iterative application of the
complexity upgrading technique becomes possible
