巡回セールスマン問題とは、「複数ある都市をセールスマンが営業で回るのに最も効率のよいルートは何か」というものを示すことで、最短ルートを近似的に想像することは出来ても理論的に（コンピュータ等で）証明するのが非常に難解で有名な問題があります。
その巡回セールスマン問題は「NP完全問題（非決定性多項式時間完全 Non Deterministic Poliminal Time Complete）」と呼ばれています。専門ではないのでよく理解できていませんが、どれほど難しいかが「充足可能性問題の計算」というNP問題の一種で示されており、それが面白い。（その筋の方にはちと古いのかもしれませんが、ここではそういう正確さは抜きにして）
充足可能性問題の例として、信じるもの（正しいと証明されたこと）のリストを作ることを考える。二つ目にリストに載る「信じるもの」は第一の「信じるもの」と矛盾しないことを確かめなければならない。その作業は1回。3つ目にリストに載る「信じるもの」は第一の「信じるもの」と第二の「信じるもの」の両方と、両者、計3回矛盾していないことを確かめなければならない。4つ目のリストに載るものは7回、5つ目は15回、6つ目は31、10つ目は1023、1000つ目は10の310乗になるそう！
それを空想上のコンピュータで計算することを考える。並列に数が多ければ多いほうがいいわけで、仮に陽子の大きさ（10の-15乗メートル）の素子を処理装置（CPUチップ見たいなもの）とするコンピュータを仮定する。すると1立方メートルで10の45乗個の素子を詰め込める。
ひとつの素子が、光の速さ÷素子の直径=3x10の-24乗で切り替わり信号を送る（=先の認証作業のひとつをこなす）と仮定すると、1秒に10の23乗の処理が出来る理論上最速のコンピュータということになる。しかし、1立方メートルで10の45乗個の素子を積んだコンピュータ計算すると、最初の1秒で225つ目までリストを作成できるが、次の226個目を認証するのにもう1秒、232番目を調べるのに1分、247番目までは1ヶ月、275番目までは3500万年！
それを宇宙誕生からこれまでの寿命10の17-18乗秒（感覚的にはこれもすごい！これだけか、というか10の18乗ってそんなに大きいのか、というか）にちょっとおまけをのせて10の19乗秒間計算するとすると、10の87乗回の計算ができるが、なんとそれでできるリストは289個にすぎない！
そこでコンピューターの数を増やすしかない。ひとつ1立方メートルなどと言わず、宇宙の大きさくらいのコンピュータを作ってみる、と（これまたすごい仮説w）。およそ120-140億光年（1光年は10の13乗キロ）と言われているそうだがとりあえず1000億光年とすると、10の126乗個の素子を積んだコンピュータが出来るらしい。
その「宇宙の大きさ」で「永遠」に計算した結果、、、10の168乗回の計算が可能で、それによって出来るリストはたったの558、、。
原著は1988年（訳書は2004年）なので当時とはコンピュータ処理的に何がしかの革新（それこそ指数関数的な）が起きているかとは思いますが、専門外の僕にとってはそもそもその正確さなどはどちらでもよくて、この思考実験の発想とスケールが面白いなと思いました。しかしNP問題が難解と言われているのは今も変わらず、というかその難解さの理由が物理的な限界であるというのが驚きです。以上正月の読書より。
投稿
