近代から現代にかけて数学界では多くの難問・予想が生まれ、数多くの優秀な頭脳をもってしても明確な証明を得られぬまま、時が過ぎ去っていった。
2000年、クレイ数学研究所は主要な未解決問題を集めてリストにまとめ、1世紀ほど先んじていたダフィット・ヒルベルトの問題(1900年パリ国際数学者会議で提示された23の問題。いくつかは証明され、部分的に答がでているものもある。また解くのが不可能と証明された問題もある)と同じように7問を提示し、それぞれに100万ドルの懸賞金がかけられた。
Ⅰ バーチ・スウィナートン＝ダイアー予想
Ⅱ ホッジ予想
Ⅲ ポアンカレ予想
Ⅳ ナビエｰストークス方程式
Ⅴ P＝NP問題
Ⅵ リーマン予想
Ⅶ ヤンｰミルズの問題
現在までに、ポアンカレ予想だけが解決している。これは2003年にグレゴリー・ペレルマンが証明した。ペレルマンはこの問題にかけられていた100万ドルの賞金もフィールズ賞も辞退している。
そんな｢ミレニアム懸賞問題｣をいくつかの記事に分けて紹介しよう。
今回は複雑性理論の大御所、｢P＝NP問題｣について。
参考は↓の書籍。賢者を目指すブログ主の愛読書。
｢現代数学についてもっと知りたい！！｣って人は下記記事も参照されたし。
巡回セールスマン問題
P＝NP問題の前に、計算機数学の一大テーマ｢巡回セールスマン問題｣を取り上げよう。
あるセールスマンは、10カ所の異なる町を訪れなくてはならない。
取り得る最短経路はどれだろうか？
最良の方法として考えられるのはすべての町をちょうど1回ずつ訪れる経路だが、そのような経路が存在しないこともある。
町の数が少ないときには、試行錯誤すれば最適な経路が見つかるかもしれない。
しかし、町の数が増えると、これはただちに実現困難となる。
この問題は下記にある複雑性理論において、単純なアルゴリズムで一般的に解ける問題でないとされている。
現在までに解決されたこの問題の最大の実例は、85,900都市を巡回するという難問である。
これは1991年にグルハルト・ライネルトが提示し、2006年にデビッド・アップルゲートが解決したもので、のべ136年分のCPU時間を要した。
複雑性理論
計算機で問題を解く場合、すべてのアルゴリズムが等しく効率的というわけではない。
優れたプログラマーは与えられたタスクをすばやくこなすプログラムを上手に書くだろうが、アマチュアが頑張って同じタスクをこなすプログラムを書いても処理に何百倍もの時間がかかる。
これがアルゴリズム設計の手腕と呼ばれるものだ。
とはいえ、すべてがプログラマーの創意工夫に委ねられるわけではない。
極めて優秀なプログラマーでさえ、巡回セールスマン問題を解決するすばやいアルゴリズムは構築できそうもない。
なぜなら、おそらくそのようなアルゴリズムは存在し得ないからだ。(これが正しいかどうかは、この分野の最大の問題であるP＝NP問題にかかっている)
これが複雑性理論で取り上げるテーマだ。複雑性理論は、数学とコンピューター科学の境目にまたがっている。
主な研究対象はタスク固有の難易度であり、任意のアルゴリズムが問題を解くために費やす時間によって測ることができる。
複雑性クラスとP＝NP問題
迅速に確認できる問題はすべて、迅速に解けることも可能だろうか？
P＝NP問題が意味するところは、大雑把にいえばそういうことだ。
この解の価値は懸賞金100万ドルよりもはるかに高いだろう。
というのも、整数の因数分解・巡回セールスマン問題といった、アルゴリズム設計に関する数多くの他の問題に大きく影響するからだ。
クラスPは、多項式時間内で｢解決｣できるすべての問題の集合だ。例えば、ある数が素数であるかどうか判定するような問題がある。これらタスクは、n個のデータ入力に対して、アルゴリズムのステップ数がnの2乗や3乗のような多項式で与えられる。(Pは｢polynomial：多項式｣の頭文字)
クラスNPは、数の因数分解など、多項式時間で｢確認｣できるような問題の集合だ。NPは｢non-deterministic polynomial time：非決定性多項式時間｣のことで、これは非決定性のコンピューターを使うと(運がよければ)すばやく解決できるだろうという意味である。例えば、10531532731のような大きな整数を多項式時間で因数分解できる既知のアルゴリズムはない。だが、101149×104119がその答えであると教えてもらえれば、それが正しいことを確認する作業にはほとんど手間がかからない。
Pに含まれるすべてがNPにも含まれることは簡単に分かる。(P⊆NP)
100万ドルの問題はNP⊆Pであるかどうかだ。
数学者やコンピューター科学者の間では概ね、P≠NPではないかと考えられている。
では、P≠NPだとしたらどうなるだろうか？
P≠NPならば、NPに含まれる問題には多項式時間で計算できないものがあることになる。
こうした問題には、従来とは違う、量子コンピューターを用いた量子アルゴリズムによる量子多項式時間で解決できるかどうかが、次の段階の研究として重要になってくる。
～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
ここで紹介したのはP＝NP問題に関する大まかな知識である。
もっと知りたいと思ったら、専門書を目印に、｢数学の森｣の奥深くに進んでみよう。
目指せ！！未確認問題動物(笑)！！これぞ賢者への道程！！
コメント