情報学基礎理論

計算の限界

21世紀数理科学の最難問、コンピュータの「計算限界」に挑む


渡辺治先生

東京工業大学 理事・副学長(研究担当)


◆研究のきっかけは何ですか

最先端のコンピュータを使っても計算できないと予想されている「計算の限界」問題が存在します。よく知られているのは巡回セールスマンという問題です。

セールスマンが複数の都市を1回だけ巡回し出発地に戻る経路の中で、最短経路を求めよという問題です。一見簡単な問題です。しかし都市数が増えた場合、しらみつぶしに計算する方法では、超強力スパコンで宇宙年齢ほど年数をかけても、解を見つけられない場合があります。しかも、それより本質的に早い一般解法は存在しない、つまり実質的には計算不可能な問題と言われています。実は、そうした問題が数千、数万とあります。なぜ、そういう「計算限界」があるのかを知りたくて研究を始めました。

◆どんな成果が上がりましたか

私たちは、暗号理論、量子コンピュータ、高性能計算など、数理科学の国内外頭脳を結集し、計算限界に挑み、情報学基礎の学問分野に全く新しい扉を開きました。「なぜ、計算限界があるのか?」について真正面から取組み、様々な種類の計算限界を解析し、困難さを解明すると同時に、逆にどの程度まで簡単になるかも追及し、計算効率の限界解明の糸口を見出してきたのです。

◆その研究が進むと何が良いのでしょう

計算の限界問題の解決により、我々の「計算」に対する理解は、大きく進展するでしょう。それによって、数理科学に新たな分野が開かれるはずだと考えます。今より優れた暗号が開発されるかも知れないし、コンピュータに乗せるより効率のいい、優れた計算手順の発見に結びつく可能性があります。

悪い計算手順を使うと1兆年かかってしまうものも、よい計算手順を使うと、1秒でできてしまうという例もざらにあるのです。そこを目指しています。

SDGsに貢献! 〜2030年の地球のために

image

「計算」の限界を探る研究をしてきました。コンピュータで、例えば最短経路の計算をするのに、計算法(アルゴリズム)次第で、処理速度には大きな差が出ます。でも計算法にも限界があります。

「その限界を見極め、不可能性を証明したい」という、純粋に科学的な興味からの研究です。「できない」を証明して何の意味があるの?と思われるかも知れませんが、その解析の中から「計算」の重要な側面が明らかになり、驚異的な計算法が発見されることもあります。それがビッグデータ解析などにも使われているのです。

この道に進んだきっかけ

中学の頃「プログラム」という不思議な人工言語でコンピュータを動かすのだと知って以来、プログラムにはまりました。工夫次第でいろいろな事ができるので、面白かったです。ただ、コンピュータの計算には何らかの限界があるのでは、と漠然と思っていました。

大学1年生の時、図書館で面白い数学書はないかと探していたら、『計算の理論』(M.デービス著、渡辺茂・赤摂也共訳)という不思議な本に出合い、その「解読」(正に解読なのです!)をした結果、そこには計算不可能性の証明が解説されているのだとわかり、感動しました。

今はそんな「解読」をしなくても、計算とは何かをもっと手軽に知ることができます。例えばYouTube で「cs101x」を検索してみてください。

どこで学べる?
もっと先生の研究・研究室を見てみよう

image

講義の様子

学生はどんな研究を?

多くの学生は、様々な計算問題に対して、アルゴリズムの設計をしたり、その計算困難さを解析する理論研究を行っています。ただし「計算」にかかわることであり、本人が強く希望すれば、コンピュータによる実験やシステム開発などの研究も認めています。各々が対象とする問題は異なりますが「計算」の本質や重要な側面を理解したい、という点では目標は同じです。

具体的な計算問題の例(卒業論文、修士論文で行った研究)としては、下記となります。

・充足可能問題の指数時間高速解法

・データベース中の頻出アイテム集合の列挙問題

・論理証明系に基づいたパズルゲームの計算困難さ

・グラフの到達可能性問題

学生はどんなところに就職?

◆主な業種

・ソフトウェア関連

◆主な職種

・ソフトウェア開発者(設計・開発)

先生からひとこと

「計算」とは何か?の入門コースを、YouTubeで公開しました(「cs101x」で検索)。計算の原子にあたるものは?ということから始めて、最新の計算論の研究やデータサイエンスやAIの話まで語っています。講義#1のあと、一気に講義#19~を見るのもいいですよ。

中高生におすすめ

コンピュータサイエンス 計算を通して世界を観る

渡辺治(丸善サイエンスパレット)

情報処理の本質は「計算」である。ここでの「計算」とは、単純な演算や判断の組合せで表わされる処理のこと。そしてコンピュータサイエンスとは、様々なこと、つまり、物理現象も生命現象も社会現象も、すべてを「計算」として見ようとする。

この見方=「計算世界観」はこれまでにない新たな見方であり、情報処理の本質をさらに深く理解するためにも、重要な見方である。だからこそ、教養としてコンピュータサイエンスを学び、計算世界観の考え方に触れて欲しい。東京工業大の1年次の教科書だが、全体としては比較的気軽に読める。


思考する機械コンピュータ

ダニエル・ヒリス(草思社文庫)

コンピュータというと、電子回路や半導体など電子機器としての側面に目が行きがちだ。しかし、実はコンピュータというものを理解するためには、コンピュータ上で実現される情報処理の本質を知ることの方が、重要である。

コンピュータ科学者である著者は本書で、その情報処理の本質に関わる概念や考え方を、単刀直入かつ具体的な実例を使って、分かりやすく説明してくれる。また、著者の経験や逸話などが交えられており、読み物としても楽しめる。


先生に一問一答
Q1.日本以外の国で暮らすとしたらどこ? 

ドイツ連邦共和国。自然との調和を大切にしている国だから。

Q2.感動した映画は?印象に残っている映画は?

最近では『ボヘミアン・ラプソディ』がよかったです。うーん、と思ったのは『猿の惑星』のエンディングですね。

Q3.会ってみたい有名人は?

イエス(キリスト)もしくは釈迦


みらいぶっくへ ようこそ ふとした本との出会いやあなたの関心から学問・大学をみつけるサイトです。
TOPページへ