研究シーズ2018情報基礎科学

実際の⼊⼒構造を活⽤し、 より効率的に計算を行うアルゴリズムを研究

岩田 陽一情報学プリンシプル研究系 助教

研究分野離散最適化/パラメータ化計算量/⼤規模グラフ

研究背景・目的

コンピュータで計算を行うためのアルゴリズムの研究は大きな発展を遂げてきました。さまざまな問題に対して効率的に働くアルゴリズムが数多く開発されてきた一方で、その効率化に限界も見えてきました。例えば、広く信じられているP≠NP予想の下では、どんなNP困難問題も多項式時間で解くことはできません。また充足可能性問題(SAT)の難しさに関する「SETH」という仮定を用いると、グラフ理論における「到達可能性クエリ」を従来の方法より良くすることはできないのです。しかし、これらの効率化の限界は想定し得る全てのケースを考えた場合の限界であって、実際に扱いたい特殊なケースに限れば、必ずしもあてはまるわけではありません。また、対象が非常に大規模なグラフだったとしても、到達可能性クエリなど、効率的に処理できているものもあります。そのような実際の応用時に現れる特殊なケースに対して、効率的に働くアルゴリズムの開発とその解析を行っています。

研究内容

17-iwata-02.jpg

「一般には難しい」=「とても難しい入力が存在」全部が難しいわけではない

産業応用の可能性

研究者の発明

連絡先

岩田 陽一[情報学プリンシプル研究系 助教]
yiwata[at]nii.ac.jp ※[at]を@に変換してください

Recommend

さらにみる