活動情報

イベント詳細

第11回セミナー・勉強会

日時: 2021.06.07 Mon. 10:00-12:00
会場: オンライン
話者: 岩政 勇仁(京都大学,C01班)
題目: 制約充足問題に対する代数的アプローチ
概要:
制約充足問題 (Constraint Satisfaction Problem, CSP) とは,与えられた制約を全て充足する変数割当が存在するか否かを判定する問題である.CSP は一般的に NP 完全であるが,制約に現れる関係に制限を加えることで多項式時間可解な部分クラスが得られることもある.Feder-Vardi は 1998 年に,関係に制限を加えることで得られる問題は P か NP 完全のどちらかであるという予想(二分予想)を提唱した.この予想は長らく未解決であったが,2017 年に Bulatov と Zhuk により独立に肯定的に解決された.本講演では,二分予想の証明において重要な役割を果たした代数的アプローチについて概説する.
2021.05.25 更新