「二分決定グラフ」の演算にかかる最悪時間計算量を証明～計算機科学分野の数十年来の未解決問題を解決～ | ニュースリリース | NTT

◆二分決定グラフは集合の集合を圧縮して表現することができるデータ構造です。これまで最悪時間計算量が未知であった二分決定グラフの多数の演算について、入力のサイズに対して演算の実行に指数的に時間がかかる事例が存在することを示しました。 ◆本発見は今後二分決定グラフを用いた応用において、正しく計算量を見積...