今日の一言/2013-1-25

かりこみ条件

高邊くん論文がプレプリントサーバーにアップされる．

ちょっとボサボサの庭木があったので，剪定しようと考えた．ぱっと見て伸びている枝を見つけると，また伸びてくると面倒なので，その付け根の一歩先まで刈りとることにする．そうすると近くにまた伸びている枝を見つけて．．．ちょっと説明に無理があるなぁ．

ランダムグラフ上の制約充足問題をグラフの端っこの方から制約を決めながら解いていくことを考える．解けた部分は消していく一連の手続きを続けた結果，全てのグラフを消し去ることができると正確な充足解が見つかる．ランダムグラフの次数を増やしていくと，この手続きではかりこみ切れない状況に陥る．具体的にhypergraph上のVertex cover問題について，このかりこみ可能な境目の次数を熱力学極限で正確に評価したのが高邊くんの研究である．その値はレプリカ法というまったく別の解析で現れるレプリカ対称性の破れが起こる条件とぴったり一致することを見つけた．レプリカ対称性の破れとかりこみアルゴリズムの限界が一致するいう不思議な現象です．