本講演では最小頂点被覆問題と呼ばれるランダムグラフ上の組合せ最適化問題の典型的な困難さについて述べる. この問題の統計力学的解析から,グラフの平均結合数がある閾値を超えるとレプリカ対称性の破れが生じることが知られ,厳密なアルゴリズムの平均求解時間に関する転移との関連が示唆されている[1]. 一方で,近似解法として重要な線形緩和を問題に適用すると,典型的な近似精度に関してもある種の相転移が存在することが数値的に示唆されている[2]. 我々はこの線形緩和の挙動を統計力学的手法を用いて定量的に解析することで,典型近似精度に関する相転移が存在し,その閾値がもとの問題でレプリカ対称性が破れる閾値と等しいことを明らかにした[3]. 講演ではその詳細を報告し,計算の困難さとグラフ構造との関連性について議論する予定である.
[1] M. Weigt and A. K. Hartmann, Phys. Rev. Lett. 84, 6118 (2000).
[2] T. Dewenter and A. K. Hartmann, Phys. Rev. E 86, 041128 (2012).
[3] S. Takabe and K. Hukushima, J. Phys. Soc. Jpn. 83, 043801 (2014).