集中講義北海道大学2008

2008年度　北海道大学　集中講義

講義題目:　位相空間のトポロジーから見る相転移と最適化問題

講義担当:	福島孝治(東京大学大学院総合文化研究科)

日時:		2008年12月9日-10日

概要:
最適化問題や制約充足問題のように，複数の条件を同時に満足する多数の状態
変数の探索問題は，絶対零度の統計力学に類似していることは古くから指摘さ
れてきた．特に、近年，ランダムな制約条件のもとでの多くの問題が，制約条
件の数をパラメータとして変化させたときに，解の性質が劇的に変化すること
が見出され，多体問題の相転移現象と関連して勢力的に研究されている．全く
制約条件のない問題では状態空間の全てが解であるのに対して，制約条件を増
やすことで解の状態空間が減っていき，やがて全てが消滅することになる．こ
のような状態空間のトポロジーやジオメトリーの変化を統計力学の観点から眺
めてみる．この集中講義では，統計力学の相転移理論の基本的な考え方から始
め，ランダム系の統計力学の手法であるレプリカ法の解説から，制約充足問題
の例を示す． 　

1．はじめに
   最適化問題，制約充足問題の例とそれらの相転移の様子

2. 平衡統計力学による相転移理論
   統計力学のいろは，イジングモデルの相転移，平均場理論，ランダム
   グラフ上のイジングモデル．

3. 制約充足問題の解空間
   ランダムなK-XORSAT問題の解析，SAT-UNSAT相転移，解のクラスター化

4. さいごに
　他の制約充足問題の数値計算による研究，講義で触れなかったopen problems 
　
この講義に関連するが，ほぼ独立な話題をセミナー形式で初日の夕方に予定し
ている．
%%%%%%%%%%%%%%%%%%%%%%%
数独の統計力学的研究
福島孝治(東京大学大学院総合文化研究科)

数独は日本の雑誌で有名になり，現在では世界的によく知られていてる単純な
パズルである．解くべき問題は，9×9のマスの中の各行，各列にそれぞれ1か
ら9までの数字を一つだけならべ，その中の3×3のブロックにも一つだけ数字
を入れる．これは典型的な制約充足問題であり，制約条件に適当なエネルギー
関数を導入することで，統計力学的には少し変わった格子構造上のポッツ模型
とみなすことができる．我々はこの問題の統計力学的性質をモンテカルロ法を
用いて調べた．例えば，一般のn×nマスに拡張し，全くヒントがない場合の数
独の解の個数を統計力学的に数え上げることができた．また，数独を解く難し
さと熱力学的性質の関係について議論する．
%%%%%%%%%%%%%%%%%%%%