「隣」の分野の知見に注目して成果を出す

　吉田悠一助教の専門分野は、理論計算機科学である。例えば、ある問題を計算機が解く場合の「計算量」を調べ、それが解ける問題なのか、解けない問題なのかを調べる学問分野だ。

　その吉田助教は現在、「実用的なアルゴリズム」、つまり計算機で実際に動作させた時に高速なアルゴリズムの研究にも手を広げる。というのも、吉田助教が理論計算機科学の立場から計算機科学分野のアルゴリズムの世界を見た際に「驚くほど手がついていない状態」であることに気づいたからだ。つまり、未解決の問題の宝庫に見えたというわけだ。

　例えば、データベース分野で高速なアルゴリズムの研究は進んでいるが、それが「なぜ高速なのか」を理論的に解明する研究は手つかずの部分が多かった。

　「理論に基づく高速なアルゴリズムができれば、より有用性が増します。また、理論の発展は、現実のコンピュータを相手にする計算機科学の研究者にも、大きな刺激となるはず。アルゴリズムに理論を持ち込むことにより、自分自身が、従来分野の研究者に刺激を与えるような"黒船"になりたいのです」と、吉田助教は話す。

　吉田助教がこのように語る背景として、今、異なる研究分野を「越境」する研究が盛んになっていることがある。

　「ブレークスルーのためには、いろいろな分野に触れることが不可欠です。違う分野でこそ、良い問題、良い道具が見つかりやすい。実際に、数学の分野である表現論や代数幾何学の研究者が、理論計算機科学の問題を解くといったこともある。逆に、黒船に乗り込まれてしまうこともあるのです（笑）」

　例えば物理学もその1つ。現在、多くの物理学者が複雑ネットワークに関心を持ち、その性質を研究している。この研究領域から出てきた概念に「グラフの頂点をどれだけ最短路が通っているか」で頂点の重要性を評価する「媒介中心性」がある（図１）（図２）。感染症の流行のモデル化に使ったりと応用範囲が広いが、計算量が大きくなることから、高速アルゴリズムの研究対象となり得る。「他分野の知見をアルゴリズム研究に使わないのはもったいない」と吉田助教は力説する。

定数時間アルゴリズムのすごさ

　吉田助教が研究者として取り組む中心的なテーマは、「定数時間アルゴリズム」の研究である。その基本的な考え方は、問題のサイズに関わらず、一定の時間で解くこと。つまり、問題のサイズが巨大になるほど、この定数時間アルゴリズムは恐るべき威力を発揮するようになる。

　例えば、SNSのFacebookをモデル化してグラフとして表すと、ユーザー数と同じ約10億の「頂点」を持つことになる。このグラフの「直径」（グラフのすべての頂点の組み合わせの中で最大の距離）を正確に求めるには、計算機の処理速度を毎秒1億ステップとして約2万年もの計算時間が必要となる。現実的には解くことが不可能な問題なのである。

　ところが、誤差ε=0.01、つまり1％の誤差を許容して、ある定数時間アルゴリズムを使って解くと、同じ問題の解が1.2ミリ秒と、ほぼ一瞬で求まる。2万年が1.2ミリ秒に短縮されるということは、現実には解けなかった問題が、解けるようになることを意味する。これが定数時間アルゴリズムの威力だ。

　このアルゴリズムを現実世界に応用できれば、今までできなかった処理ができるようになる。有用性という観点で見ても、恐るべき可能性を秘めた理論だろう。

　一方、吉田助教の関心は現実世界への応用よりも理論へ向いている。最近の研究では、ある問題が「どんな性質なら定数時間に解けるか、解けないか」を追究し、「その必要十分条件を与える」という成果を挙げた。定数時間アルゴリズムの本質に関わる理論を証明したのだ。その証明の過程では、「調和解析」という数学の道具を使った。ここでは逆に、理論計算機科学が数学の成果を取り込んだ格好だ。「これも隣の分野の成果を使った研究の例です」と吉田助教は話す。

プログラミングコンテストが取り持つ縁

　現在、吉田助教は、「ERATO（戦略的創造研究推進事業・総括実施型研究）河原林巨大グラフプロジェクト」において、「複雑ネットワーク・地図グラフグループ」のグループリーダーを務めている。このグループの構成メンバーは、「プログラミングコンテスト出身のアルゴリズムの達人揃い」なのだという。この研究グループから生まれた新しいアルゴリズムとして、グラフ内の任意の2点を結ぶ最短距離を既存手法の100倍も高速に解く「Pruned Landmark Labeling」がある。このアルゴリズムでは現実世界のWebを観察した知見を取り入れた。Webのリンクをモデル化した「Web Graph」は、多くの頂点が集まる「コア」と周辺領域にあたる「フリンジ」と呼ぶ構造を持つ（図3）。そしてグラフ上の2点の最短経路はこのコアを通ることが多い。この知見を元に理論を駆使し、高速化に成功したのだ。

　このアルゴリズムの論文は、吉田助教と、東京大学大学院博士課程に在学中の秋葉拓哉氏、岩田陽一氏の3人で書かれた。皆、ACM-ICPC（ACM国際大学対抗プログラミングコンテスト）の出身者だ。アルゴリズムを理解し、プログラムを組む訓練を積んできた若者たちが今、理論計算機科学において、アルゴリズム研究の最前線を担っているというわけだ。

　最新理論に基づくアルゴリズムの研究は「計算機ができること」の範囲を大きく広げ、現実の世界に衝撃的な変化をもたらす可能性がある。ITが社会の隅々まで浸透する中、理論計算機科学の成果への期待はますます高まっている。

（取材・文=大河原克行）