歴代受賞者一覧

受賞者紹介

渡辺 治（わたなベ・おさむ）
昭和33年3月3日生まれ
東京工業大学工学部情報工学科 助教授

贈賞の理由

計算の複雑さの構造的解析とその応用に関する研究

コンピューターが対象とする問題には、それぞれ本質的にもっている“難しさ”があります。このような“難しさの本質”に迫るのが「計算の複雑さの理論」で、コンピューターサイエンスにおける最も基礎的な研究分野です。この中でも、とくに、問題の難易度を、それぞれに共通な性質を見つけながら分析していく研究を「計算の複雑さの構造解析」と呼ぴます。渡辺助教授は、この分野で数々の重要な貢献をしてきました。

この分野の中心的課題は、非決定性多項式時間問題の難しさの解析です。この問題のクラス（クラスNP）には、人工知能からVLSl設計まで、情報処理のさまざまな分野にかかわる問題が含まれていますが、その解析は難しく、多くの問題が未解決のまま残されています。なかでも、クラスNP内の難しさのレベルの差や、難しさの度合いが重要な未解決問題といわれています。

渡辺助教授は、指数時間問題のクラス（クラスE）が、クラスNPに類似していることに目をつけ、1987年に、クラスE内に難しさのレベルに基づくある種の階層構造が存在することを証明しました。これにより、今まで単なる予想にすぎなかったクラスNP内の階層性に、明確な証拠を与えました。現在、この方法論は多くの研究者に利用されています。さらに、クラスNPの中でも「NP完全」と呼ばれる問題群に対し、その難しさの度合いを調べ、1990年には同僚の荻原氏とともに、今まで知られていた結果を大幅に改良する結果を得ました。この結果は、NP完全問題の難しさを解明する大きな一歩として評価されています。

計算の複雑さの構造解析は、暗号の安全性解析に応用することができます。暗号化に使う関数には、事実上破られることがないくらい複雑であることが要求されます。渡辺助教授は、複雑さの構造的解析の手法を用い、暗号解読の難しさの尺度をいくつか提案し、さらに、それらの尺度のもとで、どの程度までの難しさを保証できるか、という問題を解明してきました。さらに、暗号の解読がある種の学習に相当することから、同様に、学習の難しさを解析する理論的枠組みも提案しています。

このように、渡辺助教授は、コンピューターサイエンスの最も基礎の分野で、研究発展の強力な推進役を果たしてきました。

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