主成分分析を用いたK-SAT問題における相転移現象の可視化

概要

論文の詳細を見る
研究では,充足可能性問題 (random K-SAT 問題) の相転移現象を数値シミュレーションにより検証する.K-SAT 問題は標準的な NP 完全問題であるが,K-SAT 問題における相転移現象については未だ明らかになっていない.解析的には,系のサイズ (ブール変数の次元数) が無限大の場合に部分的に解かれているのみである.本研究では,Markov chain Monte Carlo(MCMC) シミュレーションと主成分分析 (PCA) を組み合わせた手法により,K-SAT 問題の系の経験分布を直観的に理解しやすい 2 次元ヒストグラムの形で表現し,その際の固有値分布についても示す.また,磁化の値やスピングラス秩序変数のヒストグラムについても示し,K-SAT 問題の相転移現象について議論する.シミュレーション結果より,3-SAT 問題において低温状態の hard-SAT 相当の条件下では,混合相 (磁化が非零でレプリカ対称性が破れている) となることが示唆されたが,さらなる詳しい検証が必要である.
2011-08-29