歴代受賞者一覧

受賞者紹介

宮野　悟（みやの・さとる）
昭和29年12月5日生まれ
九州大学理学部基礎情報学研究施設　教授

贈賞の理由

並列計算量理論の研究

効率のよいアルゴリズムの開発は、コンピューターサイエンスの最も重要な課題です。そのため、この30年近くにわたって多くの研究がなされ、いわゆる逐次型計算機に関しては、NP完全性や多項式時間計算可能な問題のクラスPなど、効率化の指針を与える豊かで有用な研究がなされてきました。また、逐次型計算機の限界を克服するためにいくつかの並列計算機も提案され開発されています。しかし、問題によっては、そのような並列計算機上で高速に解けるものと、本質的に逐次的であり効率のよい並列計算が期待できないものとがあることが判明しています。こうした並列計算による計算の効率化とその限界を究明するのが、並列計算量の理論です。宮野教授は、この分野で極めて重要な貢献をしてきました。

クラスPの計算の仕組みをある意味で代表する問題を「P完全な問題」とよんでいます。P完全な問題は、効率的な並列化がほぼ確実に不可能な問題と理解されているものです。宮野教授は、まず、極大部分グラフを求める問題に対して、非常に一般的な形のP完全性定理を証明しています。このことから、逐次アルゴリズムによって多項式時間で計算可能な極めて多くの問題に対して、効率のよい並列化は困難であることが明らかになりました。

この定理は、P完全性についての世界ではじめての一般的な結果であり、同様な問題に対して個々にP完全性を証明する必要がなくなりました。さらに、これまで効率のよい並列化が知られていなかった非常に広い範囲の問題に対して、効率のよい並列アルゴリズムをもつことを組織的に証明し、効率のよい並列化が可能であることも明らかにしています。そして、こうした研究等を基礎にして、宮野教授は数人の協同研究者を得て、並列学習アルゴリズムの研究とそのゲノム情報処理への応用、特に、タンパク質データからの機械発見システムの開発を行い、その実験の成果は分子生物学の分野でも高く評価されています。

このように宮野教授は、並列計算量の理論というコンピューターサイエンスの重要な基礎について顕著な業績を挙げ、その発展に大きく貢献しました。

上に戻る

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