  Zero-suppressed binary decision diagram (ZDD) is a data structure to
represent a family of (sub)sets compactly, and it can be used as a succinct
index for a family of sets. To build ZDD representing a desired family of sets,
there are many transformation operations that take ZDDs as inputs and output
ZDD representing the resultant family after performing operations such as set
union and intersection. However, except for some basic operations, the
worst-time complexity of taking such transformation on ZDDs has not been
extensively studied, and some contradictory statements about it have arisen in
the literature. In this paper, we show that many transformation operations on
ZDDs cannot be performed in worst-case polynomial time with respect to the size
of input ZDDs. This refutes some of the folklore circulated in past literature
and resolves an open problem raised by Knuth. Our results are stronger in that
such blow-up of computational time occurs even when the ordering, which has a
significant impact on the efficiency of treating ZDDs, is reasonable.
