歴代受賞者一覧

受賞者紹介

戸田　誠之助(とだ・せいのすけ）
昭和34年1月15日生まれ
日本大学文理学部応用数学科　助教授

贈賞の理由

数え上げ計算の複雑さに関する研究

計算の複雑さの理論は、NP完全な問題の発見をはじめとして「計算」に対する重要な知見をもたらし、コンピューターサイエンスの最も重要な基礎となっている。しかし、計算に対する理解はいまだに十分には深まっておらず、P≠NP予想のような問題は、今のところまったくといっていいほど解決への手がかりがない。

戸田助教授は、計算の複雑さのクラスの構造に関する研究、特に数え上げ計算の複雑さの研究において以下に述べるような衝撃的な結果を独創的手法で証明することに成功し、この「計算」に新たな理解をもたらした。

NPはハミルトン経路問題のように「ある特定の条件を満たす解があるか」を問う問題のクラスである。戸田助教授の研究した数え上げ計算問題?PP問題?は、そのNP問題を多少一般化したものとして1970年代の終わりころ計算の複雑さの理論の中に登場した。NP問題が解の存在を問う問題であったのに対し、PP問題は「ある特定の条件を満たす解が何個あるか」を問う問題である。「解」の個数がわかれば解があるか否かもわかるのでPP問題はNP問題の一般化になっているといえる。

戸田助教授は、この単純な一般化が、実は計算の複雑さを大きく変えていることを見出したのである。NPの上には非常に複雑な形の最適化問題などを含 む多項式時間階層(PH)と呼ばれる計算量クラスの階層がある。当時、PPはこのPHの低い階層に位置する問題と同程度の計算複雑さしかもたないだろうと予想されて いた。しかし、同助教授は、PPには、すなわち解の個数という情報には、このPHの計算をも含むような大きな計算能力があることを証明してみせたのである。 この結果はそれまでだれも想像だにしなかった深い知見を「計算」に対して与えた。また、その証明法は、確率的な解析を戸田の多項式と後によばれるようにな った多項式を用いて代数的に解析するというもので、その解析法もまた計算の複雑さに関する様々の研究に応用され大きな反響を呼んだ。この業績は理論的コン ピューターサイエンスの最高峰の研究に位置付けられるものである。

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