|
高橋です。
| > S O_u propto R＾N
| > これを「複雑さのギャップ」と呼ぶのならばこのギャップは厳然
| > として存在します。
|
| わたしも大ざっぱな話し大好きです．
| 上は，$O_u$を１タイムステップに必要な計算量として，
| 一つ前の計算結果を保持するなどの「マジックを使わない場合」
| $O_u propto sum_{S} R(S)^N$
| の意味ですね．しかもこれは，原理（群）が独立な場合ですね．
|
| もう少し，スペシフィックな話しをする時，もしくは
| 現象の計算論的な複雑さを比較する時には，他の指標が良いでしょう．
要は問題がNに関してNPだということをいいたかっただけなので
R^N なのですが、それともう一つ古典力学系が念頭にあったからと
いうのもあります。つまりは多体問題です。この宇宙は
その最小構成要素(仮にアトムと呼びます)
をプロセッサとした超並列系だと考えることができます。
その場合には各々のアトムは一最小時間ごとに全ての他のアトムとの
相互作用を計算し、次の時刻の自分の状態を決定します。
量子論等で場を導入する場合にも、時空量子化理論かなにかで時空を
離散化すれば、アトムをlatticeに置き換えることで同じことがいえます。
# 赤方偏移の量子性の議論が結着したのかどうかわからないのと、
# 時間の量子化はまだ完全ではないのでちょっと弱いですけども
このときには、系自体が実際に行っている計算は最適化とは
無縁なので、やはりRとNのみに関係するとおもいます。
| リアプノフ指数から導くこともできます．
リアプノフ指数から計算量を導くわけですか？
この分野は勉強をはじめたばかりなので具体的なやり方が
イメージできません。ヒントでいいので教えてください。 :-)
慶應義塾大学s 環境情報学部 (Bioinformatics Lab.) ‾‾‾‾‾‾‾‾‾‾‾‾‾
高橋 恒一
＿＿＿＿＿Kouichi Takahashi t94249kt@***.*** ＿＿＿＿＿＿＿
----- |
|
|
