研究 / Research

情報学プリンシプル研究系

岩田 陽一
IWATA Yoichi
情報学プリンシプル研究系 助教
学位:情報理工学 博士(東京大学)
専門分野:数理情報
研究内容:https://researchmap.jp/y_iwata/
研究室WEB

サイエンスライターによる研究紹介

計算が難しい問題の「難しさ」を究める

「 難しさ」を明らかにしたい

今の研究の中心は、「NP 困難問題」の「困難」の程度を明らかにすることです。NP 困難問題とは、問題の規模が大きくなっていったとき、必要な計算時間があまりにも増大するため、実際にコンピューターで扱うことが困難な問題です。たとえば「横n 行・縦n 列の碁盤目になっている道路があるとき、同じ地点を通らずに左上から右下に行く経路は何通り?」という問題は、4 行・4 列までなら人間が手で図を書いて経路を数え上げていくことが可能です。しかし10 行・10 列となると、同じ方法で数え上げるためにはスーパーコンピューターでも数年かかります。経路の数が、問題の規模とともに爆発的に増大していくからです。
問題の大きさに比例する時間で解ける問題は、コンピューターが倍速くなれば倍の大きさの問題が解けます。一方、問題の大きさに対する指数時間が必要な問題では、コンピューターが倍速くなっても同じ時間で解ける問題サイズはほんのわずかに増加するだけです。従って、アルゴリズムを改良することに大きな重要性があります。
今、取り組んでいる課題は主に「NP 困難問題では、規模が大きくなったときに計算時間が非常に多くなるのは仕方ないけれども、少しでも計算量を減らし、しかも『だいたい』で妥協せずに厳密に解ける計算方法を開発する」と「理論上計算量が大きいにもかかわらず、なぜか現実の入力に対しては高速に動作する手法に理論的な説明を与える」の2 点です。
NP 困難問題では、どこかに計算の限界があるのは明らかです。でも、限界がどこにあるのかは分かっていない問題もたくさんあります。数年前、「ハミルトン閉路」という有名なNP 困難問題で、50 年ぶりに新しい計算方法が開発され、従来の手法よりも指数的に高速な計算が可能になりました。ちなみに先ほど例に挙げた問題は、現在はより高速な計算方法が発見されており、現在は17 行・17 列に対しても、パソコンで数十分かければ数え上げることが可能です。

原理と現実の接点を求めて
iwata_1.png

現実世界の中には、「理論的には、非常に計算量が大きくて実質的に解けないのと同じ」「少し計算量は大きいけれども、現実的に計算できる」「ほとんど計算しなくてよい」といった問題が入り混じっています。計算という面で見ても、現実は「きれいごと」ではありません。理論どおりの部分・部分的に理論通りの部分・理論を持ちださずに済む部分が入り混じっています。
コンピューターが計算を求められるのは、世の中の人々が心から「解きたい」と思っている問題です。このような問題では、あらゆる入力の可能性を考える理論の世界とは異なり、現実世界に即した何かしらの構造を持った入力のみが与えられることが多いのです。何がその「解きやすさ」につながっているのかを明らかにし、「解きやすさ」を決めている背景の構造も分析していき、その構造を活用できる計算方法を開発すれば、似たような問題の多くに活用できるでしょう。
大学院博士課程までは主に理論研究を行っていましたが、これからは理論研究で得られた知見を活かして、実際に世の中の計算を速くする応用にも力を入れていきたいと思っています。

PDFをダウンロード


構成=サイエンスライター・みわよしこ

注目コンテンツ / SPECIAL