最先端のアルゴリズム理論の研究開発を通じ
実社会の幅広い課題解決に貢献

脊戸　本研究室では、最先端のアルゴリズム理論を研究しています。アルゴリズムとは、問題を解くための計算手順や戦略のことで、アルゴリズムを工夫することによって計算時間を何十倍、何百倍も短縮することができます。特にビッグデータなどの大規模な処理・解析においては高速かつ高効率な計算を実現するアルゴリズムが不可欠です。

アルゴリズムにはさまざまな種類があり、毎年新しいアルゴリズムが発表されるほど研究スピードが早い分野です。取り扱うデータ量も加速度的に増大し、従来のアルゴリズムでは処理に時間がかかり過ぎたり、効率的に処理できないケースも増えています。こうした状況に対応するため、最適解ではなくても、最適解にできるだけ近い近似解を高速に求める近似アルゴリズムなども存在します。

理論計算機科学は、コンピュータによる計算を数理モデルとして扱い、数学的に研究する分野で、私はその中でもアルゴリズムの設計とその性能（アルゴリズムが解を求めるまでの計算時間や必要な領域=メモリ量）を理論的に解析することや、コンピュータが効率的に解くことのできない問題にはどのような問題があるのかについて研究をしています。

アルゴリズム設計には、さまざまな技法が存在しますが、アルゴリズムが必ずこの計算時間以内に解を求めることができるということを示すためには、アルゴリズムができるだけシンプルであり、なおかつ計算時間の解析が可能である必要があります。そうでなければ、アルゴリズムが正しく動作することを保証することが難しくなるのです。こういった点に気をつけながら取り組む問題の本質をつかみ、アルゴリズム設計をしています。

本研究室のもうひとつの役割は、計算機科学（コンピュータ・サイエンス）と応用技術（エンジニアリング）の間をつなぐ実装技術（Art：アート）の領域を確立することです。

例えば、現実の問題は複雑な条件が多く絡まっているため、最適解を計算することは非常に難しいことが多いです。しかし、問題を解くことを諦めるわけにはいかないので、様々な技術を駆使して問題の解決を図ります。これらの技術開発の研究は数多く行われています。

一方、理論計算科学では、問題を単純な形で数理モデル化し、その上でアルゴリズムを考え、動作の保証や計算時間・精度の解析を行っています。その1つに前述した近似アルゴリズムの研究などがあります。どちらも重要な研究領域ですが、応用と理論という形でこれまではそれぞれ別の研究領域とみられることが多く、これらの間をつなぐ中間的な研究開発がうまく機能していませんでした。本研究室は、文部科学省 科学研究費補助金による「社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化」のプロジェクトに参画しており、Art層での理論・技術の進化や、アルゴリズム設計のための方法論を体系化する研究に取り組んでいます（解説1）。

脊戸　理論計算機科学をベースに、厳密アルゴリズム、充足可能性問題、回路計算量などを研究しています。

理論計算機科学分野には多くの仮説があり、それらについての検証が常に行われています。現在、私が取り組んでいるのは、「強指数時間仮説(Strong Exponential Time Hypothesis：SETH)」（解説2）と呼ばれる仮説に関する研究で、これは和積標準形論理式の充⾜可能性問題に対する仮説です。

この仮説を仮定すると、さまざまな問題の既知の計算時間がこれ以上理論的に改良できないことが示されます。つまり、理論的には同じ計算時間の別のアルゴリズムは作れるかもしれないが、本質的に今よりも高速なものを作れないことを示唆しています。これは非常に厄介です。しかし、強指数時間仮説には懐疑的な研究者も一定数いて、私もその一人です。そのため現在はこの仮説の否定に向けて、さまざまな角度から研究を実施しています（解説3）。

理論計算機科学には大きな未解決問題が存在しています。それはクレイ数学研究所がミレニアム懸賞金問題の1つとしてあげている「P vs. NP問題（解説4）です。これはまだ理論的には証明されておらず、長年の未解決問題となっており、日々、世界中の研究者がこの解決につながる鍵を得ようと研究を行っています。

SETHは、このP vs. NP問題よりもさらに強い主張をしている仮説で、SETHが本当に正しいのか、主張を覆す弱点がどこかにあるのではないかというのは、研究者として非常に興味を惹かれるところです。

アルゴリズムの理論や技法は社会のさまざまな場面で活用されています。例えば、発電所から各家庭へ電気を送る電力網の最適化、１票の格差を平準化する選挙の区割り、工場の生産計画の策定、宅配便の配送ルートの検索など、私たちの身近なところでアルゴリズムを使った解析や処理が行われています。暗号などのセキュアなシステムでは、安全性を保証するための「アルゴリズムの保証」も求められます。さまざまな仮説を検証することは、アルゴリズムをさらに進化・発展させるためにもとことん追求しなければならないテーマです。一般的に「そうじゃないか」と考えられている仮説に対し理論的な証明を試みることは、アルゴリズム研究の重要な役目でもあると思います。

脊戸　アルゴリズム研究にはさまざまな領域があり、アルゴリズムそのものを開発するだけでなく、計算時間の解析やアルゴリズムが正しく動作することの理論的な証明、仮説の検証などさまざまなテーマがあります。私が取り組んでいるSETH以外にも多種多様な仮説が存在しています。近年はコンピュータのプログラミングを学ぶ人も増えていますが、アルゴリズムはプログラミングに欠かせない要素であり、幅広く奥深いアルゴリズムの世界に興味を持つ人が増えると嬉しいですね。パズルを解いたり、難しい問題を自分で解決することが好きな人には向いている分野だと思います。

情報科学研究院は多様な分野の研究室が集まっているユニークな大学院で、本研究室のように理論的な研究に携わることもできます。情報系を志望しているけどプログラミングはちょっと苦手という人にも面白い研究テーマを見つけることができると思います。また、純粋な理論だけでなく、前述のArt層の研究のように実社会への応用を視野に入れた技術開発につながる研究もできます。そういう点では、新しいことや未知のことに出会える魅力的な研究分野だと思います。

(2023/09/28)