NTTは2月19日、計算機科学の未解決問題を解決したと発表した。同社が解決したのは、著名なデータ構造として知られる「二分決定グラフ」に関する未解決問題。今回示した理論は、計算機科学の著名な教科書にあった記述の誤りを指摘しており、研究チームの修正案が承諾され、内容が改訂されるという。 二分決定グラフとは、集合のあつまりである「集合族」を表現するデータ構造だ。例えば、集合{1, 2}と集合{2, 3}からなる集合族は、{{1, 2},{2, 3}}と表現できる。集合族は汎用性が高く、さまざまなデータ構造を表現する際に使われる。その例には、ある地点から別の地点までの移動経路の組合せや、同時に利用可能なクーポンの組合せなどがある。 ネットワークの通信パターンを表現する集合族、二分決定グラフの例 図では16個の通信パターンを16個の集合からなる集合族で表現し、それを11個のノード(節点)を結ぶ線から
