担当 : 山下 洋史

題目 : The Chaos within Sudoku (文献紹介)

概要 :
充足可能性問題(SAT)は，計算機科学の基本的な問題として最も重要な問題の１つであり，これを解く SATソルバーの開発が盛んに行われている．しかし，節をランダムに追加していく状況では，変数に対する節数の割合がある閾値を超えると frozen transition と呼ばれる相転移が起こり，現在開発された全てのソルバーが SAT の判定を効率的には行えなくなることが知られている．近年，このSAT を連続時間の決定論的ダイナミクスを用いて解く手法が提案された[1]．このダイナミクスでは SATの解のクラスターがダイナミクスのアトラクターに対応する．また，frozen transition の下では，その軌道が transient chaos(過渡的なカオス) となる．

SATの難しさはこの transient chaosな軌道に表れるという仮説を立てることができる．このことを実証するため，SATとして定式化された数独パズルをこのダイナミクスを用いて解き，transient chaos の持続時間を表す指標である escape rate を数独の難易度の指標とすることが提案された[2]．また，人の手によってつけられたパズルの難易度とこの指標の比較が行われ，相関があることが確認された[2]．

参考文献 :
[1] Maria Ercesy-Ravasz and Zoltan Toroczkai. “Optimization hardness as transient chaos in an analog approach to constraint satisfaction”. Nature Physics, 7, 966. 2011.
[2] Maria Ercesy-Ravasz and Zoltan Toroczkai. “The Chaos Within Sudoku.” Scientific Reports, 2, 725. 2012.