HOME > 研究紹介 > コンピュテーション研究室

研 究 紹 介
コンピュテーション研究室homepage
情報数理分野 脊戸 和寿 講師

計算限界の解明と革新的計算手法の創出

コンピュータはどんな問題でも高速にかつ正確に解くことのできるのか?答えはNOです。しかし、高速に解くことができないからといって諦めるわけにはいきません。 逆に、暗号のように、そもそも高速に解くことができると非常にまずい問題も存在しています。
本研究室では、どういった問題が高速かつ正確に解くことができないのか?解けない問題に対して、革新的な計算手法は存在しないのか?これらの解明に向け、コンピュータの計算限界を探求する研究を行っています。

1. コンピュテーション研究室の研究テーマ

コンピュテーション研究室では理論計算機科学の計算量理論という分野を中心に研究をしています。理論を中心に研究をするので、数学力や論理思考力が強く要求されます。また計算機による実験を行い、そのデータを元に理論を確立していくという研究も行います。

計算限界に関するテーマ
・回路計算量に関する研究(論理回路の計算能力の解明)
・通信複雑さに関する研究(複数人で通信を行える計算モデルの能力解明)
革新的計算手法の創出に関するテーマ
・大規模グラフの性質に関する研究
・量子コンピュータの計算能力に関する研究
その他のキーワード
ゲーム理論、情報理論、符号理論、証明複雑さ、数理論理学など。

2. 計算限界に関する研究

計算限界の研究で最も重要な研究の1つはP vs. NP問題に対する研究です。
P vs. NP問題は、リーマン予想やポワンカレ予想などの6つの数学上の未解決問題とともにクレイ数学研究所がミレニアム懸賞金問題として提示した問題です。その懸賞金の額はなんと100万ドルです。
P vs. NP問題は簡単にいうと「問題の答えをみつけること」と「答えがその問題の答えかどうかを検証すること」のどちらが難しいか証明せよ、という問題です。直感的には答えが与えられているのだから検証する方が簡単に思えそうですが、未だにそのことを証明した人はいません。
また、P vs. NP以外にも(懸賞金はかかっていませんが)同じようにどちらが難しいのか?を問うた問題は山ほどあります。
これらの山のようにある問題を1つ1つ解明していくことで、P vs. NP問題の解決に少しでも貢献できることを目標に研究室では研究をすすめています。

3. 革新的計算手法の創出に関する研究

近年、ビッグデータを有効利用しようというニーズが増えてきています。しかし、これまでの計算手法を用いていては、あまりの膨大なデータの量のために計算が終わらないといった状況が出てきます。しかし、ビッグデータの11つには何かしらの性質があるはずです。その性質を解明し、性質を利用することでビッグデータを扱える計算手法を創出することは可能なはずです。本研究室ではWebグラフをはじめとする複雑ネットワークに対して、ネットワークの性質やそのネットワーク上で可能な計算の研究を行っています。
またそれ以外にも量子計算という量子コンピュータ上での計算手法がどの程度これまでのコンピュータの計算よりも優れているのか、といった研究も行っていく予定です。

copyright(C) Seikei University. all rights reserved.