【第222回】 計算機と数学林 悠帆 （数学）

　最初のコンピュータが発明されてから、かれこれ70年が経とうとしている。今やコンピュータはどこにでもあり、誰もが使うことのできるものとなった。しかし、コンピュータを日本語に訳せと言われたら、意外と困る人が多いのではないのだろうか。コンピュータは一般的に電子式計算機と訳され、その名の通り人間には不可能な高速演算を可能とするものである。コンピュータの発達により、その補助を得ることで多くの数学的な疑問は解明されてきた。しかし、相変わらず数学上の問題は多く、コンピュータを利用するが故の問題というものもまた、登場してくることとなる。

　そんな問題の一つとして、巡回セールスマン問題という有名な問題がある。セールスマンがある場所から出発し、いくつかのポイントを経て帰ってくる。そのときの最短経路を求めよという問題である。この問題を厳密に考えるとすると、すべてのルートに対して移動距離を計算し、最短経路を探すこととなる。経由するポイントが少なければコンピュータはすぐに最短経路を導き出すであろうが、経由するポイントが数百などとなってくると計算にかかる時間は膨大なものとなってしまう。他にも、大きな数の素因数分解も解くのに膨大な時間がかかってしまうことが知られている。この性質は暗号にも使われている。

　このような、求めるのに膨大な時間がかかる問題に「本当に短時間で求める方法はないのか？」という疑問に対し、100万ドルの賞金がかけられている。数学に限らず、「○○ができる」ということの証明は簡単だが、「○○はできない」ということの証明は難しい。まさにその代表例のような問題である。興味があれば「P≠NP予想」について調べてみよう。