The Complexity of Processing Hierarchical Specifications
Daniel J. Rosenkrantz, Harry B. Hunt · SIAM Journal on Computing · 1993
Hierarchical object descriptions consisting of a set of module descriptions are considered, where each module is either a primitive module or has a body that is an interconnection of submodules. The description represents a flattened object, whose size can be exponential in the size of the description. The complexity of processing and/or analyzing such hierarchically specified objects is considered. The simulation of hierarchically specified circuits is emphasized, but the results are applicable to other kinds of hierarchically specified objects. It is shown that hierarchically specified acyclic circuits can be simulated deterministically in space linear in the size of the description, even when the description is not explicitly acyclic. $\Theta (n^2 )$-size-bounded reductions are given from the languages in ${\operatorname{DSPACE}}(n)$ to the problem of simulating hierarchically specified acyclic monotone circuits. This implies that this simulation problem is PSPACE-complete and that any algorithm for it that operates faster than $2^{O(\sqrt n )} $ deterministic time could be used to recognize all ${\operatorname{DSPACE}}(n)$ languages in less than $2^{O(n)} $ deterministic time. It is then shown that the simulation problem for hierarchically specified acyclic circuits (not necessarily monotone) can indeed be solved in $2^{O(\sqrt n )} $ deterministic time. Moreover, every hierarchically specified acyclic circuit is shown to have an equivalent flat circuit of size $2^{O(\sqrt n )} $. For binary circuits the size of the equivalent flat circuit is $O(n^{{3 / 2}} 2^{1.53\sqrt n } )$. It is also shown that the problem of simulating hierarchically specified circuits is EXPSPACE-complete for cyclic circuits.