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

最先端のコンピュータを使っても計算できないと予想されている「計算の限界」問題が存在します。よく知られているのは巡回セールスマンという問題です。
セールスマンが複数の都市を1回だけ巡回し出発地に戻る経路の中で、最短経路を求めよという問題です。一見簡単な問題です。しかし都市数が増えた場合、しらみつぶしに計算する方法では、超強力スパコンで宇宙年齢ほど年数をかけても、解を見つけられない場合があります。しかも、それより本質的に早い一般解法は存在しない、つまり実質的には計算不可能な問題と言われています。実は、そうした問題が数千、数万とあります。なぜ、そういう「計算限界」があるのかを知りたくて研究を始めました。
◆どんな成果が上がりましたか
私たちは、暗号理論、量子コンピュータ、高性能計算など、数理科学の国内外頭脳を結集し、計算限界に挑み、情報学基礎の学問分野に全く新しい扉を開きました。「なぜ、計算限界があるのか?」について真正面から取組み、様々な種類の計算限界を解析し、困難さを解明すると同時に、逆にどの程度まで簡単になるかも追及し、計算効率の限界解明の糸口を見出してきたのです。
◆その研究が進むと何が良いのでしょう
計算の限界問題の解決により、我々の「計算」に対する理解は、大きく進展するでしょう。それによって、数理科学に新たな分野が開かれるはずだと考えます。今より優れた暗号が開発されるかも知れないし、コンピュータに乗せるより効率のいい、優れた計算手順の発見に結びつく可能性があります。
悪い計算手順を使うと1兆年かかってしまうものも、よい計算手順を使うと、1秒でできてしまうという例もざらにあるのです。そこを目指しています。
「計算」の限界を探る研究をしてきました。コンピュータで、例えば最短経路の計算をするのに、計算法(アルゴリズム)次第で、処理速度には大きな差が出ます。でも計算法にも限界があります。
「その限界を見極め、不可能性を証明したい」という、純粋に科学的な興味からの研究です。「できない」を証明して何の意味があるの?と思われるかも知れませんが、その解析の中から「計算」の重要な側面が明らかになり、驚異的な計算法が発見されることもあります。それがビッグデータ解析などにも使われているのです。
中学の頃「プログラム」という不思議な人工言語でコンピュータを動かすのだと知って以来、プログラムにはまりました。工夫次第でいろいろな事ができるので、面白かったです。ただ、コンピュータの計算には何らかの限界があるのでは、と漠然と思っていました。
大学1年生の時、図書館で面白い数学書はないかと探していたら、『計算の理論』(M.デービス著、渡辺茂・赤摂也共訳)という不思議な本に出合い、その「解読」(正に解読なのです!)をした結果、そこには計算不可能性の証明が解説されているのだとわかり、感動しました。
今はそんな「解読」をしなくても、計算とは何かをもっと手軽に知ることができます。例えばYouTube で「cs101x」を検索してみてください。

「情報学基礎理論」が 学べる大学・研究者はこちら
その領域カテゴリーはこちら↓
「13.IT・AI」の「53.ハード・ソフト(OS、アプリ)、プログラム系」
◆渡辺先生の講義 #1 コンピュータサイエンス入門概要(YouTube)
講義の様子
多くの学生は、様々な計算問題に対して、アルゴリズムの設計をしたり、その計算困難さを解析する理論研究を行っています。ただし「計算」にかかわることであり、本人が強く希望すれば、コンピュータによる実験やシステム開発などの研究も認めています。各々が対象とする問題は異なりますが「計算」の本質や重要な側面を理解したい、という点では目標は同じです。
具体的な計算問題の例(卒業論文、修士論文で行った研究)としては、下記となります。
・充足可能問題の指数時間高速解法
・データベース中の頻出アイテム集合の列挙問題
・論理証明系に基づいたパズルゲームの計算困難さ
・グラフの到達可能性問題
◆主な業種
・ソフトウェア関連
◆主な職種
・ソフトウェア開発者(設計・開発)
「計算」とは何か?の入門コースを、YouTubeで公開しました(「cs101x」で検索)。計算の原子にあたるものは?ということから始めて、最新の計算論の研究やデータサイエンスやAIの話まで語っています。講義#1のあと、一気に講義#19~を見るのもいいですよ。
![]() |
Q1.日本以外の国で暮らすとしたらどこ? ドイツ連邦共和国。自然との調和を大切にしている国だから。 |
![]() |
Q2.感動した映画は?印象に残っている映画は? 最近では『ボヘミアン・ラプソディ』がよかったです。うーん、と思ったのは『猿の惑星』のエンディングですね。 |
![]() |
Q3.会ってみたい有名人は? イエス(キリスト)もしくは釈迦 |