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.