つまり、核爆発のシミュレーションのための計算はどんなコンピュータを使っても処理しきれないくらい複雑なプロセスが必要だということだ。
セールスマン巡回問題
同様に、コンピュータを使っても解くのがほぼ不可能で、数学者にとっても難問である問題の１つに「セールスマン巡回問題」と呼ばれるものがある。
これは所定の特定の都市のリストから逆戻りすることなしに（つまり来た道を折り返すことなしに）すべての都市を1回ずつ訪問するための最短経路を見つけよという問題だ。
これがなぜ難問かを具体的な数字を使って紹介しよう。
例えば、訪問先が3都市なら、（3×2×1）/2＝3通りの選択肢から最短経路を選べばよい。
これが訪問先が10都市になると、（10×9×8×7×6×5×4×3×2×1）/2＝1,814,400通りの選択肢となる。
そして、この選択肢の数は当ブログにおいてはもはやお馴染みの指数関数的な増加をみせる。
11都市なら約2000万、12都市なら約2億4000万、そして、20都市なら100京（1兆の100万倍）を超える。30都市くらいになるとスーパーコンピュータでも（この計算方法で行うと）何億年も処理にかかる数字となってしまう。
この手の問題は、NP完全問題 (NP-complete problem)と呼ばれている。
NP完全問題とは
NPはNon-deterministic Polynomialの略で、「非決定論的に多項式時間で」という意味だ。
といわれても、これではなんのことかよくわからない。
というわけで、１つ１つ意味不明な言葉をひもといていこう。
まずは多項式（polynomial）。
これは、定数および変数（代数の文脈では「不定元」）の項（term）の和と積のみからなる式だ。
例えば、
- 3x3 - 7x2 + 2x + 23
は多項式で、この場合、"3x3" 、"-7x2"、"2x"、"23" が項にあたる。
しかし、この例をみてもわかるように、多項式関数には、指数的増加の兆候となる指数関数（例えば、y=2x）そのものは含まれていない。
つまり、多項式時間で解ける問題は、規模が大きくなればそれなりに解くのに苦労するようになるが、それを解くのにかかる時間は比較的ゆっくりとしか（といっても程度の問題ではある）増加しない。
では、「非決定論的に」というのは一体なにか？
それを考えるには原理的にすべての計算が可能であるチューリングマシンが決定論的チューリングマシーンであることを思い出していただくとよい。
ようするに、「非決定論的に多項式時間で」解くことのできるNP完全問題は、非決定論的コンピュータという仮想機械があったとしたら解くことのできる問題というわけだ。
しかし、残念ながらすべてのコンピュータはチューリングマシン同様に決定論的なので、指数関数的に増加する時間をかけることなく、NP完全問題を解くことはできないのだ。
NP完全問題は世の中にあふれかえっている！
という具合に、NP完全問題については、わかったようなわからないような状態だろうが、時間もないので先を急ごう。
次は、なんでNP完全問題が出てくるの？って話だ。
それは世の中にはNP完全問題があふれかえっているからだ。
はじめに登場した『量子コンピュータとは何か』から世の中に実在するNP完全問題の例をピックアップしよう。
- 数センチ四方のコンピュータチップや数キロに広がる通信ネットワークの中で、いかにして最も効率的に配線するか
- 飛行機の飛行計画をいかに効率的に組むか
- 生産ライン上の一連の作業をいかに効率的に配置するか
- ソフトウェアの設計。何百万というプログラム・コードの中には、必ず矛盾点があるはず。iTunesで音楽を聴いているときにワープロの上でDeleteキーを押すと、ちょうどそれと同時にEudoraでメールチェックをしていたときに限ってシステムが落ちるかもしれない
- 社会における基本ソフトウェアは、個人の行動を制限する法体系だ。複雑に絡み合った法体系は、何百年以上にもわたって肥大化し続けてきた。矛盾や不一致は、プログラムのバグと同じで避けようがない。裁判や国会審議といった絶え間ないベータ･テストによって多くの条項は削除されてきたが、その分新しい条項が次々と導入されている
バグ･フィックスをいくら行っても次々に新しい条項が追加されるなら、いくらテストに時間がかけられたとしてもきりがない。そもそも、この問題はスーパーコンピュタを使っても処理しきれないNP完全問題なのだ。
バグがすべて取り去られた完璧な状態を望むほうがどうかしているのだ。
批判が批判を産む批判の複利的増加
そもそも「過去ログを全部読んでからじゃないと批判するな」がまかり通ると、ブログ界において批判されるのは、最近ブログを始めた過去ログの少ないごく一部の人だけじゃないか？
ほぼ毎日更新をする人のログを、わざわざ全部読破してまで相手の批判をするような奇特な人は、何人もいないのではないか？
確かに、ekken♂さんのいうとおりだ。そんなことしてたら１つの批判をするのに大変な時間がかかってしまう。
それでも速読に長けた人なら、批判の機会が２回３回となったところで、それに費やす時間は「多項式時間で」しか増えないのかもしれない。
しかし、大抵の場合、批判は次の批判を産むことになる。そうなると、読まなくてはいけないブログ・エントリーは膨大になる。
そして批判が同時に複数の批判を産む、複利的増加傾向を示すようになれば、一気に指数関数的世界へまっしぐらだ。
しかも、批判をする以上、とうぜん、自分の過去のエントリーや過去の批判と矛盾するようなことを書けば、そこに批判は集中することになる。
他人の書いたエントリーの複数の文脈、そして、自分自身の発言の中の文脈、さらには後から追撃してくる批判者のこれまた膨大な数の文脈の組み合わせの中で、最適な批判を繰り出そうとすれば、もはやそれはどんなNP完全問題もかなわない最強のNP完全問題だ。
そうなると、もう批判の渦巻く渦中から抜け出す術を見出すのはこの上なくむずかしい。
ちょっとした気軽な気持ちで批判をするのは、どう考えても避けたほうがよさそうだ。
この記事へのコメント
ダウト
P!=NPは証明されましたか?
gitanez
>P!=NPは証明されましたか?
どの問題に対してですか？
いずれにせよ、証明はしていませんし、そういう主旨のエントリーではないことはわかると思いますが。
主旨が伝わらなかったのであれば、私の書き方が拙かったのかもしれません。