[4R1-OS-13] AIと制約プログラミング

[4R1-OS-13-03] 二分決定グラフ上の単一の集合族演算の計算量について

〇中村 健吾¹、西野 正彬¹、伝住 周平¹ (1. NTT)

キーワード：二分決定グラフ、計算量、集合族

二分決定グラフ(BDD)やゼロサプレス型二分決定グラフ(ZDD)は集合族を小さく表現するデータ構造で，集合族の圧縮索引として利用できる．索引化したい集合族を表現するBDD/ZDDを構築するために，BDD/ZDDを入力とし，それらが表現する集合族に共通部分・和集合などの演算を施した集合族をBDD/ZDDとして出力する変形操作がよく用いられる．しかし，一部の基本演算を除くと，BDD/ZDDにそのような変形操作を施す際の最悪計算量は未解明であった．本発表では，多くの集合族演算に対応する変形操作が入力BDD/ZDDサイズの多項式時間では実行できないことを示す．これらの演算には，Knuthが提唱したfamily algebraに現れる演算をすべて含むほか，過去の文献では多項式時間で実行できるとされていたものも含んでいる．本結果は，集合族を表現するBDD/ZDDを構築する際の指針を与えるという点で実用上も意義深い．