[講演者] 高邉 賢史氏（名工大）

[日時] 8 月10日

[場所] 慶應大学日吉キャンパス第２校舎221号室

[テーマ]：古典計算に関する計算複雑性: 講義とセミナー

13:00- 14:00 「講義1」計算複雑性理論の基礎

14:15-15:15 「講義2」計算複雑性と統計力学

15:30-16:30 「セミナー」

タイトル：組合せ最適化問題に対する近似アルゴリズムの典型性能評価と相転移現象

アブストラクト：

計算複雑性理論によれば組合せ最適化問題の多くは多項式時間での厳密な求解が困難（NP困難）と考えられている．これは問題のすべてのインスタンス（入力）に対する最悪評価に基づいている．一方で，この結果はNP困難問題のインスタンスをランダムに与えた場合にそれらが高い確率で多項式時間で求解可能であることを否定するものではない．このように，最適化問題の困難さには最悪評価と典型（平均）評価の二種類が存在する．これは最適化問題に対する近似アルゴリズムの近似精度の評価においても同様である．

統計力学の文脈では，ランダムスピン系に対するスピングラス理論に基づいた最適化問題の典型的性質の解析が活発になされている．これらの解析はレプリカ対称性と最適化問題の典型的な困難さに対する興味深い示唆を与えてきた [1]．本講演では，最大カバー問題と呼ばれる組合せ最適化問題に着目し，その統計力学的な性質の解析，および従来は困難であった近似アルゴリズム間の典型近似性能の比較について概説する．本講演の内容は福島孝治氏（東京大学），前原貴憲氏（理化学研究所）との共同研究 [2]である．

[1] R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Nature, 400, 133 (1999).

[2] S. Takabe, T. Maehara, and K. Hukushima, PRE, 97, 022138 (2018).