[4R1-OS-13] OS-13

[4R1-OS-13-03] On the complexity of single family algebra operation on binary decision diagrams

〇Kengo Nakamura¹, Masaaki Nishino¹, Shuhei Denzumi¹ (1. NTT)

Keywords:Binary decision diagrams, Computational complexity, Family of sets

Binary decision diagrams (BDDs) and zero-suppressed BDDs (ZDDs) are data structures to represent a family of (sub)sets compactly, which can be used as succinct indexes for families. To build a BDD/ZDD representing a family of sets to index, there are various transformation operations whose inputs are BDDs/ZDDs and output is a BDD/ZDD of the family after performing a set operation on the families represented by the inputs. However, the worst-case time complexity of these transformations is unknown for most of the operations. In this paper, we prove that most operations cannot be performed in worst-case polynomial time in the sizes of input BDDs/ZDDs. These include all operations in family algebra raised by Knuth, except for some basic ones. Moreover, these also include some operations that were claimed to be performed in polynomial time by previous works. These results give us guidelines for constructing a BDD/ZDD representing a desired family of sets.