つながるコンテンツ

智のフィールドを拓く トビタつための星 可能性を照らす道 未来を探るひきだし 明日へとつなぐ鍵 変化をひらくドア 研究の壁をこえたとき Moyapedia
おとなりの研究者
慶應義塾大学
理工学部 数理科学科
教授

横浜市立大学
データサイエンス学部
准教授

日本大学
文理学部情報科学科
教授

日本大学
理工学部数学科
教授

電気通信大学
名誉教授

file 01:理論計算機科学とは?

ある問題があり、それがNというサイズであるとします。この問題を「何ステップで解けますか?」ということが、問題の難しさを決めています。

理論計算機科学では、ある問題がNというサイズに関する多項式で解けるか、解けないかということが、たいへん重要なことなんですね。たとえば多項式Nの10乗といった数であれば、指数(10)のところがNに依存しないので、それほど大きな数にはなりません。一方、2のN乗という数になると、飛躍的に増大してしまう。試しにNに100を入れてみてください。理論計算機科学では、多項式解でとけないものは、どんなにがんばっても絶対に動かせない、つまりプログラムとして走らせることができないんです。

一般に、多項式時間で判定可能な問題群をPと呼んでいます。昔から数学的な大きな未解決問題として知られている、P=NP?問題は、これを扱ったものです。しかしながら実装を考えると、Nに関して線形時間で解ける、またはN × Nに関する対数を用いたアルゴリズムや計算が、今日的なターゲットだと言えるでしょう。もしP=NP?問題が解けたとしても、それが現実のアルゴリズムに何かインパクトを与えるというわけではないんですね。