NTT、計算機科学の未解決問題を解決　著名教科書の「二分決定グラフ」に関する誤りを指摘

公開 2025年02月21日 12時55分

更新 2025年02月21日 13時53分

[ITmedia]

印刷する

　NTTは2月19日、計算機科学の未解決問題を解決したと発表した。同社が解決したのは、著名なデータ構造として知られる「二分決定グラフ」に関する未解決問題。今回示した理論は、計算機科学の著名な教科書にあった記述の誤りを指摘しており、研究チームの修正案が承諾され、内容が改訂されるという。

　二分決定グラフとは、集合のあつまりである「集合族」を表現するデータ構造だ。例えば、集合｛1, 2｝と集合｛2, 3｝からなる集合族は、｛｛1, 2｝,｛2, 3｝｝と表現できる。集合族は汎用性が高く、さまざまなデータ構造を表現する際に使われる。その例には、ある地点から別の地点までの移動経路の組合せや、同時に利用可能なクーポンの組合せなどがある。

ネットワークの通信パターンを表現する集合族、二分決定グラフの例　図では16個の通信パターンを16個の集合からなる集合族で表現し、それを11個のノード（節点）を結ぶ線からなる二分決定グラフに圧縮して表現　（左）4個の点をつなぐネットワークの模式図と16の通信パターンの例、（中）通信パターンを各辺の番号を要素とする集合の集合族で表現したもの、（右）各要素が集合族中の集合に含まれている／いないの決定をノードとして持つような二分決定グラフ

　IT領域でも、回路設計や通信ネットワークの解析、AIなどで集合族は表現として使われ、それを解析する際には二分決定グラフが利用されている。そんな二分決定グラフには重要な特徴がある。ある集合族を表現する二分決定グラフに対して、さまざまな演算を適用すると“別の集合族を表現する二分決定グラフを効率的に構築できる”という点だ。

　この特徴から、例えば“経路の集合から移動距離が一定以下のものを取り出す”など、集合族に対するさまざまな操作を柔軟に実行できる。しかし、二分決定グラフに関する演算に、最悪の場合どのくらい時間がかかる可能性があるのかは、基本的な演算を除いて、多くの演算で知られていなかった。

二分決定グラフに関する二項演算の例　集合族を表す2つの二分決定グラフを入力として受け取り、それらに演算を実行した結果を表す二分決定グラフを出力

　また、計算機科学の著名な教科書「The Art of Computer Programming」（TAOCP）には“一部の演算については多項式時間（多項式で表現できる時間のこと）で実行可能である”と記載があった。しかし実際には、多項式時間で実行可能であることに関する証明は、これまで存在していなかった。

　今回研究チームでは、集合族の積（Join）の計算量が不明だった演算に着目。一度の演算の実行が複数回の共通部分・和集合演算と等価となり得ることを発見した。これを基に、一度の演算で二分決定グラフのサイズが指数的に増加する事例を示し、多項式時間で演算を実行することが不可能だと初めて証明した。

二分決定グラフのJoin演算が多項式時間で実行不可能であることの証明のポイント

　NTTはこの結果について「二分決定グラフを用いた問題解決法に適用できる、非常に影響範囲の広い理論的な成果」と説明。今回証明した理論によって、計算量の指数的な増加を防ぐために特定の演算の利用を避けるといった意思決定が可能になるという。このため、ネットワーク設計や道路などのインフラ整備の場面などで、より効率的なアルゴリズムを設計することへの貢献が期待できるとしている。

　また今回の理論は、TAOCPの誤った記述を指摘している。NTTの提案は、TAOCPの著者であるドナルド・クヌース博士も承認し、教科書の記載を改訂する予定。

印刷する