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

一种使用通用代数解决约束满足问题中的转移问题的方法

基本信息

批准号：
21K17700
负责人：
木村慧
金额：
$ 3万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2026-03-31
项目状态：
未结题

项目摘要

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

在本研究中，我们的目标是利用通用代数对约束满足问题中的转移问题的计算复杂性进行分类。作为实现这一目标的垫脚石，今年我们处理了着色问题的过渡问题，这是约束满足问题的一个子类。特别是，为了研究过渡问题的独特性质，我们考虑了具有过渡约束的彩色过渡，并开发了基于过渡约束的算法。我写的关于这个结果的手稿被第 33 届国际算法与计算研讨会（一个关于算法的国际会议）接受，并在韩国首尔发表。我们计划利用从该结果中获得的知识对约束满足问题中转移问题的计算复杂性进行分类。我们还进一步分析了去年对具有特殊代数性质的整数规划问题的解空间结构的分析，这些问题可以被视为约束满足问题的特殊情况。具体来说，当一个需要整数解的问题被放松为一个需要实数解的问题时，开发了一种方法来从放松问题的解中找到整数解，而我写的关于这个结果的手稿是一个组合优化方法，在组合优化国际会议第七届国际组合优化研讨会上被接受，并在线发表。此外，为了加深对约束满足问题中转移问题计算复杂度分类的认识，我们正在针对个别问题进行计算复杂度分析和算法开发，目前正在整理结果。此外，我们的观察构成了思考减少转型问题的基础，我们对转型问题的理解也加深了。