FC2ブログ

P=NP?

このところ頭の疲れる話題から遠ざかってましたが、ここらで少し書きたくなりました。数学の超難問について、学生時代から数学(算数?)がチョー苦手なド素人が紹介しつつ不思議がるという無謀な試みです。

ところで囲碁というゲームのルールを私は詳しくは知らないんですが、要するに碁盤の目をより多く囲んだ側が勝ち、というものだと理解しています。碁盤にはタテとヨコの線が19本ずつ引かれていて、その交点(目)に黒と白の石を交互に置いていくわけですが、仮に完全無欠の全知全能者同士が対局した場合にはどうなるでしょうか。お互いに勝つために最善の手(それ以上に良い手は考えられない、つまり全知全能者が打つべき唯一の手)を打ち合うわけだから、その棋譜はただ一通りしかあり得ないはず。ということは、勝負は両者の先手、後手を決めた段階で決まってしまうことになります。その場合、勝つのは先手?それとも後手?

これを計算しようとすると…まず最初の石を置ける目の数は19×19=361個、次に置けるのは361-1=360個…となって、棋譜は361×360×359…×2×1通り存在します。これはだいたい10の760乗という数で、この一つひとつについてしらみつぶしに調べるには当然ながら膨大な時間がかかることに。どのくらい膨大か。たとえば、世界最速とされるIBM社のスーパーコンピュータ『Blue Gene/L』ともう一つのスパコンを組み合わせると、1秒間に500兆回(5×10の14乗)の演算ができるそうです。「世界中の人々が手作業で計算するとしたら、(スパコンの1秒間と)同等の演算をこなすには何十年もかかる」ってんだからものすごい性能ですね。
だけど上記の問題をこのスパコンで計算しようとすると、1秒間に500兆通りの棋譜を調べるとしても、全ての計算を終えるには〈10の760乗÷(5×10の14乗)≒10の746乗〉秒の時間が必要(計算合ってます?)。約140億年(4×10の17乗秒)とされる現在の宇宙の年齢と比べても、その10の739乗倍はかかる計算(合ってます?)です。これじゃあ計算が終わる遥か昔に人類は滅び、それどころか宇宙はエントロピー最大の熱死状態を迎えていることでしょう。

この世界のあらゆる問題は「P」「NP」「それ以外」の3種に大別されるのだそうです。

P問題とは、「1+1」「2222年2月22日は何曜日か?」「『我輩は猫である』の作者は誰か?」みたいに、問題の答えを考えることと、それが正解かどうかを確かめること(検算)が、同じ程度の比較的短い時間(ポリノミアル=多項式時間)で可能な問題。

NP問題は上記の囲碁問題のほか、有名な巡回セールスマン問題ナップザック問題のように、問題を考える(計算する)のにかかる時間が非現実的なもの(ノンデタミニスティック・ポリノミアル=非決定性多項式時間)になりがちなのに、それを検算する時間はさほどでもないというもの。囲碁問題について言えば、解くのには宇宙の寿命をはるかに超える時間がかかるのに対して、ひとたび“最善の手”による唯一の棋譜が示されれば、それが最善かどうかを確かめるのには大した時間はかかりません。直感的に言えば、計算すべき要素が増えるにつれて計算する手間はネズミ算式に増える問題がNP問題、ということになるでしょうか。

それ以外の問題とは、「憲法を改正すべきか?」「生きる意味とは?」みたいに、必ずしも正解が明確ではなかったり、解き方や計算式がそもそも不明な問題。検算が不可能な問題と言ってもいいでしょう。このブログの一言メッセージに使わせてもらっている『銀河ヒッチハイク・ガイド』(ダグラス・アダムス著)の「人生、宇宙、すべての答え=42」なんかも代表的な例ですね。

これらのうち最大の曲者が「NP問題」。科学的に重要な問題の多くがここに含まれているわけですが、これに属する問題は形は違ってもすべて「充足可能性」という論理問題として読み替えることが可能で、これはNP問題の中でも最も難しい「NP完全問題」と呼ばれるらしい。

これをシラミつぶしではなく効率的に(多項式時間=現実的な時間内に)解く計算式は果たしてあるのか(NP問題は実はすべてP問題なのか)?というのが現代数学の難問の一つだとのこと。仮に見つかった場合、現在では時間がかかりすぎて計算不可能な科学上のいろんな難しい問題が解けるようになるので、実用的にも重要らしい。おそらくないだろう、という予測が大勢ではあるものの「ある」場合には1つ実例を示せば証明できるのに対して「ない」場合はどこまでいっても証明できないので、問題の解決は原理的に無理でしょう。

「10の○百乗」みたいな巨大な数はどんな素数の積として表せるか?なんていう因数分解もNP問題です。計算しようとしても時間がかかりすぎて現実には不可能なのに、解としてそれらの素数さえ示されれば逆に「n1×n2×n3…n99×n100(=10の○百乗)」なんて検算がコンピュータで瞬時に可能なので。これはインターネットとかのセキュリティに関わる、データの暗号化とその復元に応用されているようです。これがどっちも簡単に計算できてしまうと暗号の意味がなくなりますが、いま研究が進んでいる量子コンピュータが実現すると、どんなNP問題のシラミつぶし的計算でも現実的な時間内に終えられるようになるとのこと。自然科学や経済学の研究効率が飛躍的に上がる反面で、ほとんどの暗号が破られてしまうので、これはこれで困ったものです。

それにしても、人類にとって重要な意味を持つ難問の多くが、たった一種類の「NP完全問題=充足可能性問題」に還元できるというのは不思議な感じです。充足可能性問題の一例を挙げれば「(xでないかyである)かつ(yでないかzである)かつ(xであるかyでないかzである)」を矛盾なく満たすようにxyzの真偽を決められるか否か?なんてやつ。「∨(または)」「∧(かつ)」「~(ではない)」とかの論理記号で表される問題です。「世界は論理でできている」との思いをますます強くします。

参考:
『数学21世紀の7大難問』(中村亨著 講談社ブルーバックス)
『量子コンピュータ 超並列計算のからくり』(竹内茂樹著 同)
『パラドックス大全 世にも不思議な逆説パズル』(ウィリアム・パウンドストーン著 青土社)
スポンサーサイト



コメント

コメント(11)
No title
疲れた…。でも自分で書いてみると、本で読んだだけよりもよく理解できた気がします。

Jinne Lou

2006/01/14 20:35 URL 編集返信
No title
難しすぎて途中で分からなくなってしまいました。最後の一言「世界は論理でできている」は私はそうは思っていないだけに気になります。

凡人

2006/01/14 21:31 URL 編集返信
No title
自分も「世界は論理でできている」と確信できているわけではなく漠然とした直感にすぎないんですが、近年の物理学でも、物質はつきつめると「モノ」ではなく「コト」に還元されていくことが分かってきたらしいです。

Jinne Lou

2006/01/14 23:19 URL 編集返信
No title
「世界は論理でできている」というのは、その意味を理解することが難しいですね。そもそも論理というのは、思考の原理であり、これは、世界がどうあるかを意識において叙述するものであり、虚像のようなものという気がします。「世界は論理でできている」ということは、実物がそれを写す虚像からなっているというようなことになります。

phi*o*ophe*7*p

2006/01/17 11:55 URL 編集返信
No title
私は逆ではないかと思います。人間は世界のあらゆる側面を研究し、それを把握しようとしているのであって、すべての側面を論理として写そうとしているのではないでしょうか。世界は世界として成立っているのであり、意識の側にある論理からなるということはないと思います。むしろ世界はエネルギーからなっているというように、客観的世界のものでできている必要があるのではないでしょうか。

phi*o*ophe*7*p

2006/01/17 11:56 URL 編集返信
No title
それとも「世界は論理でできている」は、法則性のことでしょうか。

phi*o*ophe*7*p

2006/01/17 11:57 URL 編集返信
No title
まじめさんがおっしゃることは全く常識的な判断だと思います。上記コメントでも述べたとおり漠然とした直感で、説得力ある説明はできません。ただここで言う「論理」とは、モノとモノをつなぐ「関係性」みたいなものです。モノなしには存在しえないと思われている関係性こそ、逆にモノが存在するための条件なのではないかと。

Jinne Lou

2006/01/17 22:27 URL 編集返信
No title
たとえば量子力学では、同じ量子が観測者の運動の仕方によって存在したりしなかったりするという、実在論的な世界観では説明しづらい事実も分かってきているようです。主体や客体の存在よりも、むしろそれらの関係性のほうが先立つのではないかという予感です。ちょっとオカルトめいた話に聞こえるかもしれませんが。

Jinne Lou

2006/01/17 22:36 URL 編集返信
No title
ニュートンが、天体の運動に関して、神が最初の一撃を加えたと言ったようなことを聞いていますが、ここでの問題は、物体と運動とを切離して考えたことであり、物質と関係性とを切離すことに問題があるような気がします。存在すること=関係することであり、どちらが先というものではないのではないでしょうか。

phi*o*ophe*7*p

2006/01/22 08:54 URL 編集返信
No title
物質がエネルギーに還元されることはE=mc2の方程式でも明らかにされていたことです。しかし、だからといって、客観的世界が、物質ではなく精神から成立っているということにはなりません。エネルギーも物質に他なりません。レーニンが唯物論と経験批判論で、物質を、精神を除く、意識から独立した客観的実在として定義しましたが、エネルギーは物質のカテゴリで把握し得るものです。

phi*o*ophe*7*p

2006/01/22 09:44 URL 編集返信
No title
いや、関係性と精神とは違います。「世界は論理でできている」はこのスペースではちょっと説明しづらい感覚なので、興味をお持ちでしたらこんな本を読んでみてください。『可能世界の哲学』http://www.amazon.co.jp/exec/obidos/ASIN/4140017902/qid=1137904439/sr=8-2/ref=sr_8_xs_ap_i2_xgl14/503-3100642-1449547 『物質をめぐる冒険』http://www.amazon.co.jp/exec/obidos/ASIN/4140910445/qid=1137904535/sr=1-1/ref=sr_1_2_1/503-3100642-1449547

Jinne Lou

2006/01/22 13:37 URL 編集返信
コメント投稿
非公開コメント

プロフィール

Jinne Lou

Author:Jinne Lou
個人>国家
公共≠国家

月別アーカイブ