投稿元:
レビューを見る
読んで良かった。NP を語る機は熟した。なるほど。最近の動向ってどんな感じなのかなってのを期待して読んだのだけど、良く分からなかった。私が学生の頃は、geometric complexity theory が、真相に近づくアプローチとして、一時熱を帯びていたけど、どんな感じなんでしょ。少し調べてみようかな。arXiv とかに流れるデマゴーグを楽しんでいた頃を思い出す。
投稿元:
レビューを見る
難しい数式が一切出てこないので、
わりと読みやすいのだが、
たとえ話とかしか出てこないので
理解して読むにはちょいとむずかしい。
投稿元:
レビューを見る
Fermatの最終定理、四色問題、Poincare予想(すでに肯定的に解決されているので、定理と呼んでもよいのだが、ここでは伝統的な表記としました)のように、歴史的な数学的な問題については、さまざまな書籍が出ているが、P=NPほど数学的な意義が大きいにもかかわらず、一般向けの書籍化がされていないものは無いように思える。
その理由は、いくつか考えられるが、もっとも問題なのは何が問題なのかわからない(説明に非常に高度な数学を必要とする)ということであろう。
Fermat最終定理は、中学校の数学を多少思い出せばだれでも理解することができるし、四色問題に至っては小学生でも理解できる(Poincare予想は、少し位相幾何学の知識が必要であるが、この場合は、図や2次元のトポロジーにおける簡単な例をとって何となく説明できる)。
ところが、P=NPはそうはいかない。計算とは何か、という非常に抽象的な対象を理解する必要がある。
しかしながら、本書では―ここが本書の上手いところー、そういった数学的な文言は避けていて、仮にこの定理が正しいとしたら、という前提で、こんなことができるようになるんだ、というストーリーを展開している。なるほど、こんなやり方もあるのか、と感心した。
さてさて、P=NPとは前述した通り、計算にかかわる数学の予想である。
Pというのは、多項式時間内に解くことができる問題のクラスであり、NPとはそうでない問題(このように書くと少し(大分?)誤解が生じるが、これこそ一般向けの書籍が少ない理由で、これを厳密に説明しようとすると大学の数学へようこそ、となってしまう。。)
たとえば、二次方程式を考える。
我々は、今、解の公式という中学校で習った方法を使用すれば、どんなに二次方程式でも(複素数を認めれば)解を求めることができる。
例を挙げると、x^2-2x+1=0はx=1を解に持つ。
さて、今、解の公式を知らないとする(原始人とか?)。
すると、この問題はとても難しくなるだろう。
普通の人なら、xに適当な値を入れていって、解を見つけようとする。x=0を入れても成り立たないから、次はx=1を入れて・・・・というように。
上の例だとx=1でちょうど解になるので、それほど難しくないが、これが無理数が解となるような方程式だと、おそらくお手上げである。
原始人から見ると、xにたくさん値を入れて、頑張って解を探さないといけない、非常に時間を要する問題である。
一方で、現代人からみると、解の公式を使えば、ものの数秒で解くことができる、「効率的な方法」を知っている。ということになる。
この違いは、天と地ほども違うことを理解できるだろうか。
翻って、どんな問題も上の例のように、力ずくで解くよりもスマートな方法(解の公式のような)が存在するだろうか?
というのがP=NPである。
どんな問題でも、解の公式に相当するスマートな方法があればP=NP、そうではなくて、ある種の問題に対しては、どう頑張っても力ずくでしか解けないという問題が存在するのであればP≠NPとなる。
P≠NPの場合は、調べる数が増えると、指数関数的に解くための時間を要する。それこそ、宇宙ができて今に至るまでの時間の10倍とか笑
二次方程式はスマートな方法があるので、クラスPの問題である。
では、クラスNPにはどんなものがあるだろうか?
この例は、たくさんあって、有名な問題は巡回セールスマン問題、ナップサック問題やHamilton経路問題なんかがある。
巡回セールスマン問題は、日常生活でも大変重要な問題である。
たとえば、あなたがビジネスマンで、アメリカの各州に商品のセールスに行くことを考える。
今、カリフォルニア州にいて、全ての州を1回だけ訪問して、最後にカリフォルニアに戻ってくる計画を立てるとき、移動時間を最小にしたい。Time is money!
このとき、どんな経路を取れば最少となるか、というのが巡回セールスマン問題である。これはクラスNPの例であることが知られている。
この問題、現在でも解の公式のような便利な方法は提案されていない。
仮に、効率的な方法を一般にも適用できる形で提案できれば、P=NPが解決されたことになる。
そして、人類史上最高の数学者として歴史に名を残せるのだ。
巡回セールス問題を解いたからと言って、全ての問題に対して効率的な方法があるとは限らないじゃないか、と思った人、非常に鋭い。
が、クラスNPに属して、かつその問題を解くと全てのクラスNP問題にも適用できる問題があるのだ。これを特別にNP完全と呼ぶ。
上記の巡回セールスマン問題等は、NP完全問題であり、これらの中で一つでも解くことができれば、ほかの問題(Hamilton経路問題等)への拡張ができ、芋づる式にすべての問題に適用が可能で、めでたくP=NPが証明できたことになる。
すべての問題に対して、スマートは方法があると思いたいが、現在の専門家の間ではP≠NPが主流であるそうだ。
つまり、どんなに科学が進歩しようと、力ずくでしか解けない問題も存在する、ということである。
しかし、それを受け入れて、ほどほどの時間内に、ほどほど良い解を見つける方法というのも、十分検討する価値があるように思える。
おそらくこの問題は生きているうちに解決されないだろうが、P=NPなのかP≠NPなのか、とっても気になります。