Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-048 | 5th October 1995 00:00

Succinct Representation and Leaf Languages

RSS-Feed




TR95-048
Authors: Helmut Veith
Publication: 15th October 1995 13:27
Downloads: 1650
Keywords: 


Abstract:


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.



ISSN 1433-8092 | Imprint