今日の質問： 沢山出たが，ちゃんと答えられなかったね．気がつけば(いやこれはちょっとウソ)，すでに十月になろうとしている．この講 義をやってから二か月も経ってしまって，
という疑問は多いにある．しかしながら，講義を終えてから，ずーとこのページを書いていないことが心のたまっていたのは本当である． 今回は，最適化問題への統計物理からのアプローチの概論のさわりのさわりを話した．あんまりよくまとまっていなかったなー．前日まで岡山でこの手の研究会があったが，個人的には最適化関連の話が一番面白かったので，やはりこの話題に触れたかった． ファーストタッチは，Fu-Anderson(1985)であろう．NP問題の多くが形式的にスピングラス問題と同じように見えるという発見である．気づけば当り前なことではある．その後の発展は特にK-SAT問題を中心にここ数年になされていた．計算機(もっといえば人間)にとって，「問題が難しい」とはどういうことなのか?というのは興味ある問題であろう．これまでの，計算科学屋のアプローチでは主に最悪評価としての難しさの評価が主だったが，統計物理は典型的な評価を得意としていて，それもそれなりに興味のあるところであろう．
- 誰がこのページを見に来るだろうか?
- そもそも，何を話したのか覚えているのか?
最近明らかになった大きな事柄は，前者は統計物理としてはある問題を与えたときのstaticな相転移の問題であり，後者は解空間の動的な探索であり，強いて言えば非平衡問題に対応する．前者の問題への大きなニュースはおそらくR.Monasson et al, Nature 400(1999)133.であろう．その後にいろいろな最適化問題に対して，数値実験やらレプリカ解析やら沢山やられている．後者はとても難しく，アルゴリズムに依存した話なのだが，その中で普遍的な性質があるかも．．．という話になってきている．
- ある種の相転移が最適化問題にある．K-SAT問題の場合は，変数とClauseの数の比をパラメータにしたときに，解が存在する相(SAT相)と存在しない相(UNSAT相)がある．
- ある種のアルゴリズムで解を探索するときに，その相転移近傍に，問題を解くのに必要な時間のオーダーが質的に変化する．
こうした研究自体に素朴な疑問がないわけではない．統計力学的にはやはり熱力学極限をとらなければならない．というか，そこからの接近理論だと思う必要がある．計算科学の分野でどのくらいのスケールの問題が興味あるのかよくわからない．その接近法に活路はあるのか? 物理からは普遍的な性質に興味があるので，熱力学極限にその普遍的な性質があるのならばそれはそれで楽しいとは思う．
典型評価のためにはなんらかの問題のランダム化が必要であるが，それはどういうことだろうか．ランダム化からスピングラス理論への接続は自然なので，解析する方としては都合がよい．K-SAT問題ではランダム化，すなわちさまざまなClausesについての平均的な性質を議論することはそれほど問題にはならないであろうが，最適化問題としてはやはりTSPの問題ならアメリカの都市の解の性質が知りたいであろう．どうするか．．．まだまだ，問題の難しさについて，何かわかったわけではないようである．なんか，講義で話したことを書いているのか多いに疑問．手元にあるノートにはもっとSAT問題の泥くさいところが書いてある．相転移の話とか，計算時間の話とか．ちょっと面白のは，相転移点と計算時間の質的な変化点が有為にずれているところか．