グレッグ・イーガン『宇宙消失』をネットで議論

SF 理系ネタ J

http://groups.google.com/group/rec.arts.sf.written/browse_thread/thread/a34e5caee2154424/089093456497a651
１９９５年に出た定理により作中のほとんどの話が不可能になった、んだそうで。
普通の読者はまぁそこまで突っ込まないわな。

追記：こちらでリクエスト出たのでやってみます。
http://umiurimasu.exblog.jp/6892153/

量子コンピュータがある種の問題に限って通常よりはるかに効率的に計算が出来る、ということの原理の説明として以下のようなのがある。シュレディンガーの猫を使って青酸ガスをつかった「死ぬか生きるか」て分岐じゃなく、電卓を使って「数字の１か０かを見せる」という分岐を作る。それぞれに対し猫なりの簡単な計算をできるとする。０の計算をした猫と１の計算をした猫の重ねあわせができる。
放射線検知器に繋がった０１表示装置を１０個用意してみる。これを１０ビットの記憶装置と考えると１０２４通りの数字の重ねあわせができる。猫じゃなくてもっと計算の出来る機械をこれに繋げば、１０２４種類の入力それぞれに対して一台の機械で同時に計算を行える。２０台使えば１００万通りの数字に対する計算を同時に行える。つまり計算速度１００万倍！しかし、最後に結果を見ようと箱を開けると、このコンピュータはどれかの数字の結果に収束してしまい、一種類の結果しか得られない。
なんとかうまい方法を使って、意味のある計算結果ほど高い確率で収束するような方法を考えればその問題を回避できるように見える。Shorによる素因数分解のアルゴリズムはそういう感じだと思われる。

ところが１９９７に出た論文によると、こういう無数の入力に対して計算を行うというのは普通の計算アルゴリズムでは原理的に困難だということが分かったらしい。量子コンピュータの物理的性質を考慮して巧妙に設計されたアルゴリズムじゃなくて現在普通に使われてるプログラムをそのまま使うと、うまく結果を取り出す以前に計算自体が出来ないと。
追記：ちがいました。計算は出来る。でも最後にうまくいった分岐を取り出す時、ShorのアルゴリズムみたいにFFTを使ってトーナメント方式でどんどん分岐の数を半分にしていければ高速に計算できるけど、普通はそうできない。うまく干渉させて都合のいい分岐を選ぶには場合の数がｎのNP完全問題の場合、√ｎステップの操作が必要になるらしい。ｎ〜exp（問題サイズ）なので、これは多項式時間ではない。

宇宙消失の中では主人公自身がシュレ猫になり、同様に無数の入力に対し同時に行動し都合のいい結果の出たバージョンに収束する。これができなくなるということらしい。

追記：いやしかし、NP完全問題ってかなり限定されると思うんだけど。NP完全問題についてはhttp://www.scottaaronson.com/writings/limitsqc-draft.pdf がすごくわかりやすかった。ちょっと整理。多項式時間で解を求めるアルゴリズムが存在する問題の集合をPと呼ぶ。多項式時間で解けるかどうか分からないけど、ランダムに解を探してまぐれで解が出てきたらすぐ正しい解だと分かる問題の集合をNPと呼ぶ。非決定論的Pの略。まぐれP。素因数分解とかも、二つの因数をまぐれで見つけたら、それを掛け算して元の数になるかどうかは簡単にチェックできる。NPの中で一番難しいと考えられる問題がある。例えば地図の３色問題。４色だと必ず塗れることは分かってるけど、３色だと塗れたり塗れなかったりする。３色で塗り方を見つける、という問題は今のところしらみつぶしに調べる方法しか知られていない。また非常に多くの問題がこの３色問題と等価だということが知られていて、そのうちのどれか一つでも多項式時間で解くアルゴリズムが見つかれば等価な問題全てを多項式時間で解ける。この一番難しい問題の集合をNP完全問題と呼ぶ。NP完全問題を多項式時間で解ければ、他のもっと簡単なNPの問題も多項式時間で解ける。その場合はPとNPは同じ集合つまりP=NP。でも現在おおかたの科学者はそうではないだろうと思っている。ちなみに因数分解はNP完全問題より簡単な問題。
NP完全問題よりも難しい問題、つまり解があっても正しいかどうかすぐにはチェックできない問題もある。チェスの不敗戦略とか。戦略の解説書は詰みまでの手数の指数関数で長くなる。
警備員の目をすりぬける、とかいう問題は、はたしてNP完全なのか、さらに難しいのか。うーん計算の問題とは違う気がするんだけど。それに場合の数が指数的に増えるものなのか。SF的に面白い考えをすれば、あの小説では○○が収束を引き起こす設定だった。それなら○○に区別できない状態は一まとめになりそれ以上細かく収束せず重ね合わせのままじゃないんか。そういう場合の数はそんなに爆発的に多くはならない。イーガンお得意の○○原理でOKじゃないかな。

んー宇宙消失だけじゃなくてあの長編も・・・