歴代受賞者一覧

受賞者紹介
牧野 和久(まきの かずひさ)
昭和45年2月12日生まれ
大阪大学大学院基礎工学研究科システム創成専攻 助教授

離散列挙問題に対するアルゴリズムの研究

牧野氏の離散列挙問題、特に論理関数の双対化と推論補完に関する業績は、計算機科学の中心的課題での世界的なブレークスルーであり、数多くの重要な応用を持つ。数学になぞらえると、双対化問題は論理式における「方程式の解空間の構成問題」であり、推論補完は「方程式の解空間の制御問題」である。

和積型論理関数の解空間の究明は計算理論の最大課題である。その最初のステップである解の存在判定問題は充足問題(SAT)と呼ばれ、NP完全性の理論など大きな成果をもたらしている。一方、次の非常に重要なステップは、解空間の構成問題の探求である。特に単調論理関数に対しては、解空間の構成及び記述は双対化問題、すなわち積和型表現への変換問題として捉えられ、擬多項式列挙時間を持つ計算クラスを定義する。FredmanとKhachiyanによる最初のブレークスルー(1996年)以降、多くの研究者により解明が行われ、計算クラスに入る問題が個々に発見されてきたが、牧野氏は、数理計画法を用いた独自の視点により研究を進め、計算クラスの拡大・統一化を与えた。これは計算クラス全体に影響を及ぼす初めての大きな進展であり、データマイニングにおける著しい成果など多くの新しい展開をもたらした。　更に牧野氏は、非決定性ビットに注目したアルゴリズムの改良や論理式の新しい分類を行うなど、世界的に研究をリードしている。

更に進んだステップとして、推論における論理仮説の補完は、論理式で与えられた仮説と帰結に対して、条件を付加して解空間の制御を行う問題である。具体的には、仮説を充足する解は必ず帰結を満たすような極小補完を列挙する問題であり、判りやすく言うと、「事件の犯人を特定するために探すべき証拠」を指示する問題である。これは、AIや発見科学の根幹で生じる問題であるが、その巨大な計算量が知識システム設計のボトルネックであった。牧野氏は広く信じられていた予想を覆し、最も重要なクラスであるホーン推論において、逐次多項式時間での補完列挙を可能にした。

これら牧野氏の成果は、2003年度には3つの格式ある国際会議での基調講演テーマとなるなど、発見科学における日本の先進性を計算理論の面から支える成果であり、日本IBM科学賞を贈るにふさわしいものである。

※所属名および役職は、受賞時のものです。