>> 専門の「計算複雑さとアルゴリズム」とは、どんな研究ですか?

情報処理の中の問題には、コンピューターを使って「効率よく解けやすいもの」と、「効率よく解けにくいもの」があります。解けそうなのか、解けなさそうなのかを、明確に分類していくのが「計算の複雑さ」や「計算量理論」と呼ばれる分野の基本的なテーマです。

>> 「やすい」「にくい」とは、あいまいですね。

「解けるのか」「解けないのか」という原理的な議論は過去にあり、研究は進んでいます。実は、「解けやすいもの」と「解けにくいもの」は、なんとなくの感覚はあるのですが数学的に証明されるには至っていません。数学的な証明を将来的に見つけて行こうというのがこの分野の研究の目標なのです。

>> アルゴリズムとは?

「効率よく解ける」、あるいは「解けそうだ」ということがわかってきたときに、効率のよい処理方法が必要になります。それが、「アルゴリズム」です。

>> インターネット検索で使われるアルゴリズムのことですか?

それとは、ちょっと違います。Googleにキーワードを入力して検索すると、関連するページが上から順番に掲載されますが、Googleの検索に使われているアルゴリズムは、どのページを1番上に掲載して、2番目をどのページにするのかという、ページの価値を決めるためのアルゴリズム。処理方法というよりは、ある価値基準によって序列をするための評価方法なのです。

>> 専門分野は、インターネット検索とはまったく関係ないのですね。

基本的にはそうですが、ただ、キーワード検索を実行した際、膨大な数のページが分母として集められます。そのページを格納して並べたり、言語によって並べ替えたり、すべてのページをある価値基準に照らし合わせたりするときに、効率的なアルゴリズムが必要になります。そこの部分には、処理方法としてのアルゴリズムが反映されているはずです。

>> なんだか難しそうですね

実生活の中で考えると、わかりやすいですよ。

>> 例えば?

典型的な例に、スケジュールがあります。時間割を例にとると、大学規模の時間割になると、科目数も、教室の数も、先生の人数も膨大なものになります。時間割がどれだけ膨大な規模になっても効率よく作ることができるのかどうかは、実は、まだ証明されていないのです。

>> そうなのですか。

はい。効率よく解けることが証明されて、効率のよい処理方法としてのアルゴリズムが開発されれば、科目数や、教室の数や、先生の人数などの条件を設定し、コンピューターに計算させれば、自動で時間割ができるということになります。

>> それは便利ですね。

便利ですし、社会の役にも立ちます。でも、先生だって人間ですから体力には限界があります。先生の体力を無視しためちゃくちゃな時間割ができてしまったら役に立ちません。

>> 実生活の中で、研究が反映されている場面はありますか?

直接の専門ではないのですが、どうも、電車のダイヤに使われているふしがあります。

>> それは、どういうことですか?

最近のダイヤを見ていると、人間ではなく、コンピューターが作っている匂いを感じるのです。

>> 具体的にいうと?

僕は、日大文理学部(世田谷区)に来るのに京王線を利用しています。調布駅で新宿行の電車に乗って、桜上水駅で降りています。

>> 京王線を使っている学生も多いですね。

その京王線なのですが、昔は、新宿駅では、特急が20分に1本出て、急行か快速が10分に1本ずつ、その間をぬって各駅停車が出発するという感じでした。それが、今は、特急が2本連続して出発することもあります。しかも、10分間のうちに。帰りに桜上水駅で調布方面の電車を待っていると、特急が2本通過していきます。その後に、急行、快速、各駅停車がやってくるんです。また、朝は、調布駅で、急行が特急に抜かされたりします。快速なんか特急に2本抜かされるのです。ものすごく不思議なダイヤだと思いませんか?

>> 確かに、不思議です

しかも、昔と比べて特急の本数が増えていますから、遠くから新宿へ通勤する人などは便利になっているはずです。このダイヤを人間が作ったのなら、かなりの発想転換が必要になります。想像だけど、いいアルゴリズムを搭載したスケジューリングのためのソフトウェアを使っているのでは。もしそうなら、僕はすごく嬉しいです。専門と関係する分野で社会の役に立っているということですから。

>> 先生の直接の研究分野は、社会に役立つ前の段階ということですか?

一般的にはそうです。テーマは、すべての場合においてうまく処理できるのか、できないのかに分けることです。基本的には、うまく処理できないということを示そうとしているのですが、それが実はぜんぜんできないのです。

直接、社会に貢献することもある。それは、ずはり「暗号」! 暗号は解読されたら困るので、「解くことができない」ことを証明する必要があるんだ。ただ、現在のコンピューター上で使われている暗号システムは開発されてから40年ほど経っているけど、実はまだ、「解くことができない」と証明されるには至っていない。みんなが安全だろうと思って利用しているだけなんだって。ちなみに、現在の暗号システムが解読された例は、これまでにはないとのことだよ。


戸田 誠之助 Seinosuke Toda
[計算複雑さとアルゴリズム]



[教授]1984年、電通大・院・修士課程修了。1991年、東工大にて博士号取得後、電通大や日大の助教授を経て現在に至る。様々な計算法の効率の限界を理論的に分析する研究でゲーデル賞など受賞。


>> 奥が深そうですが、ゼミに配属された学生はどのように学ぶのですか?

まず、論理学か、プログラム言語かを選んでもらいます。プログラム言語も、ソフトを作るというよりは、プログラムの理論を学んでほしいです。

>> 学生は、理論的な部分を中心に学ぶことになるのですね。

はい。基礎や理論を理解するという経験を通して、筋道を立ててきちんと論証することができるようになります。本気でがんばっている学生はかなりの行数のプログラムを作ったりもしますが、基礎的なことをしっかり勉強してもらって、考え方の部分で、少しでも社会で役に立つことができる人間になってほしいと思っています。

>> どんな学生にゼミに来てほしいですか?

論理的思考能力を磨きたい人は当然のこととして、プラスアルファとして、学びたい事柄を自分で見つけ出していく人に来てほしいです。社会に出てからも必要になることですが、何を学びたいのか、どういうことをしたいのかを自主的に見つけ出していくことが大切です。

>> ゼミの卒業生は、どんな道へ進むのですか?

情報系の会社に入るケースが多いです。プログラマー、SEもいます。数学の先生を希望する学生もいます。

戸田先生の経歴に書かれた「ゲーデル賞受賞」の文字。本人に聞いてみると、「昔、たまたまちょっといい結果を出したものですから、それで表彰されてしまって」と謙遜していたけど、調べてみると、ゲーデル賞は理論計算機科学分野で優れた功績を残した人に与えられる国際的な権威を持つ賞だったんだ。ちなみに、歴代の受賞者の中で日本人は戸田先生ただひとり。

>> 先生がされている研究を、もう少し詳しく教えてください。

日常生活の中で遭遇する情報処理の問題には必ず効率よく解けないものがあるのだ、ということを証明しようとしています。この問題には、「P対NP問題」という名前が付けられています。「P」は「効率よく解ける」で、「NP」は「情報処理の問題のほとんど」となります。「P対NP問題」は、「情報処理の問題のほとんどが効率よく解けるのか」ということを定式化したものですが、予想では、「情報処理の問題のほとんどは効率よく解けない」となっており、「P」と「NP」の間には、「≠(ノットイコール)」が入ります。

>> 確か、解決した人に100万ドルの賞金が与えられる「7つの数学上の未解決問題」のうちのひとつですよね。

そうです。2006年に別の問題が、ほぼ100年ぶりに証明されたので、未解決のまま残っている6つの問題の中のひとつです。

>> 「P対NP問題」を証明しようと本気で研究している学者は世界で何人くらいいるのですか?

本気でやっている人が数人はいると思います。でも、どういう方法を使ったらいいのかすらよくわかっていない途方もない問題なのです。

>> 最後に、先生の夢を教えて下さい。

「P対NP問題」を解きたいといっても、僕が生きている間に証明されることはきっとないと思います。ただ、現在は、暫定的に「P」という、技術に依存した数学的概念を使ってこの問題を表しているだけなのです。技術が変われば、「P」そのものが変わります。それは、へたをすれば、今とはまったく違う概念を持ったコンピューターが登場するかもしれないということです。その可能性は充分あります。ただ、あったとしても誰にもわらないのですが。

>> コンピューターって、電子計算機だと思うのですが、計算そのものの概念が変わったら、コンピューター自体が今とはまったく違ったものになるということですか?

そうです。夢といったら、それが一番面白いですね。まったく新しいコンピューターに登場してほしい。



↑↑