情報理工学院 数理・計算科学系 渡辺研究室

主要な研究テーマ

私たちは「計算」を研究しています

「すべては計算で表すことができる」と叫んだら，何を血迷ったことを言っているのだ！？と思われるでしょう．場合によっては，計算高い人（←お金ずくの人）と誤解されるかもしれませんね．そこで次のように説明してみましょう．

  1. 自然現象だけでなく，社会現象や人間の行動まで，ほとんどすべてのことがコンピュータ上の仮想世界の中に実現できるようになってきた．
  2. コンピュータが行っていることは単純な計算（＝処理）の組合せである．
  3. だから，すべてのことは「計算」で表わすことができる．

こう言えば，同意できない点はあるかもしれないが，少なくとも「まあ，そういう考え方もあるかな」という気にはなるでしょう．では，ここでいう「計算」とは一体何でしょう？あるいは，物事はどういう風に「計算」として表わすことができるのでしょうか？さらには，「計算」という観点から見ることで，何か新しいことが見えてくるのでしょうか？我々は，こういった疑問に取り組んでいるのです．

以下では，その中でも，主要な３つのテーマについて簡単に解説します．（以下ではデデスマス調からデアル調に変わります．ご了承ください．）

内容項目

  1. アルゴリズムの設計と解析
  2. 計算複雑さの理論
  3. 計算世界観の追究：たとえばランダムネス（執筆中）
  4. 関連のページへのリンク

１．アルゴリズムの設計と解析

「計算」とは単純な処理の組合せである．たとえば，コンピュータに何かの仕事（※１）をさせる「プログラム」とは，そうした単純な処理をどの順にどのように組合せて目標の処理を行うかを示した命令書である．そうした命令書の元となる組合せ方の「あら筋」がアルゴリズムである．

※１：この分野では「コンピュータにさせたい仕事」のことを計算問題と呼んでいる．以下の説明でも，「計算問題」をその意味で使う．（宿題や期末試験で悩まされた「計算問題」とは別物です！こわがらないでくださいね．）

同じ仕事をするにも無数の組合せ方（＝アルゴリズム）があり，アルゴリズムによっては，効率的に処理できる場合もあれば，とてつもなく非効率になる場合もある．様々な計算問題対して（状況に応じて）最も適したアルゴリズムを設計したり，得られたアルゴリズムがどのような性能を持つかを解析する研究が，アルゴリズムの設計と解析の研究である．

質問： スパコンなどコンピュータの性能が上がればアルゴリズムの研究は不要になるのでは？

答え： その正反対！！主な理由は２つある．

理由１）　アルゴリズムの良し悪しでの効率の差は莫大だから．たとえば，良いアルゴリズムでは 1 秒で処理できるものも，悪いアルゴリズムを使うと 1 兆年かかってしまう，という例もざらにある．スパコンを使おうが，その差は埋められない．というより，スパコンをそんな差を埋めるのに使うのはもったいない．プロの世界では（あくまで比喩だが）

　　　よいアルゴリズム　→　よいプログラム　→　そしてよいコンピュータ
　　　　ここで 1 億倍　　　　 ここで 1 万倍　　　　　ここで 1 千倍

という効率向上を目指しているのだ．そのどれが欠けても目標達成はできないのである．

理由２）　世の中のコンピュータの性能が上がれば上がるほど，処理したいデータ量が増えるから．だから効率の良いアルゴリズムはますます重要になるのだ．

質問： そんなにいろいろ研究する題材があるの？

答え： もちろん！アルゴリズムの研究は他の学問分野と同様に非常に奥が深い． 確かに，これまで様々な処理に対して数々のすぐれたアルゴリズムが設計されてきた．けれども新たな計算モデル，新たな状況，新たな問題は山ほどあり，まだまだやるべきことは非常に多いのだ． また，非常に高度な数学が随所に必要となるが，これまでの数学では考えれてこなかった問題も多く，新しい数学を作り出しながら研究を進めることも少なくない．次の計算複雑さの研究でも述べるように，「計算」は，その本質はまだまだ手つかずの状態である．新しい深淵な数学の対象とも言えるだろう．

２．計算複雑さの理論

アルゴリズムの良し悪しによって計算効率に大きな差が出てくることは述べた．だから，より良いアルゴリズムを目指して研究が進められている．けれども，効率向上にも限界はある（はずだ）．つまり，計算問題ごとに「これ以上の効率は望めない」という限界があるはずだ．こうしたアルゴリズムの限界を追究するのが計算複雑さの理論である．

さて，「限界があるはずだ」と述べたが，実は，この効率向上の限界が明確に証明されている計算問題は非常に希である．限界を示すために作成した人工的な問題を除いて，我々が日常接している計算問題を考えると，そのほとんどに対して効率向上の限界が明確には示されていないのである．もしかすると，今現在用いられているアルゴリズムより，飛躍的に良いアルゴリズムが作れるかもしれないのだ．逆に言うと，それだけ「計算」についてわかっていないのである．「計算」で何ができるか，どこまでできるかが，よくわかっていないのだから．

質問： えっ，じゃあ，計算複雑さの研究をしている人たちは今まで何をしてきたの？研究してたの？

答え： この質問が一番厳しい ^^; もちろん，我々はただ手をこまねいて見ているだけではない．完全な解明にはまだ道のりがあるが，限定された形の計算のもとでの限界の証明や，難しさの関係など，いろいろと重要な結果は得られている．ただ，まだまだ道は遠い．．．

質問： でもソーティング（「与えらえた数の列を小さい順に並べよ」という計算問題）は n 個のデータには n*log(n) に比例した計算時間がかかる，ということが証明されているのでは？

答え： よくご存知ですね．そうです．ただ，それも「データに対しては大小比較だけしか行わない」という限定された計算のもとでは，の話なのだ．もっと別の計算をしてもよい，となるとわからない．効率良くできる可能性だってあるのだ．

質問： ２１世紀の数学の７大問題の「Ｐ＝ＮＰ予想」は計算複雑さの予想なのですか？

答え： その通り！これもある種の問題群に対する計算効率の限界に関する予想である．ただし，正確には「Ｐ≠ＮＰ予想」と呼ぶべき．予想は≠なので．（これについての簡単な解説は別ページＰ≠ＮＰ予想（入り口）にまとめました．）

３．計算世界観の追究：たとえばランダムネス（執筆中）

（未完成，現在執筆中）