制約充足問題の遷移問題に対する普遍代数学を用いたアプローチ

点击翻译按钮获取中文摘要

本研究では，制約充足問題の遷移問題の計算複雑さを，普遍代数学を援用することにより分類することを目指している．そのための足掛かりとして，本年度は，制約充足問題の部分クラスである彩色問題の遷移問題を扱った．特に，遷移問題ならではの性質を調査するため，遷移制約をもつ彩色遷移を考え，遷移制約に基づくアルゴリズム開発を行った．本成果に関して執筆した原稿は，アルゴリズムについての国際会議であるThe 33rd International Symposium on Algorithm and Computationに採択され，韓国ソウルにて発表を行った．この成果により得た知見を，制約充足問題の遷移問題の計算複雑さ分類へ生かす予定である．また，昨年度に行った，制約充足問題の特殊例とみなすことのできる整数計画問題に対する特殊な代数的性質をもつ問題における解空間の構造の解析をさらに推し進めた．具体的には，整数解を求める問題を，実数解を求める問題へ緩和した際に，緩和した問題の解から整数解を求める手法を開発していたが，この成果に関して執筆した原稿は組合せ最適化についての国際会議であるThe 7th International Symposium on Combinatorial Optimizationに採択され，オンラインにて発表を行った．さらに，制約充足問題の遷移問題の計算複雑さ分類に関する知見を深めるため，個別の問題に対する計算複雑さ解析やアルゴリズム開発を進めており，結果がまとまってきているところである．また，遷移問題における帰着を考える上で基礎となる観察を行い，遷移問題に対する理解が深まってきている．