Challenge to Sigma-2P complete problems: moving up in the polynomial hierarchy

对 Sigma-2P 完整问题的挑战：在多项式层次结构中向上移动

• 批准号: 22K19813
• 负责人: 横尾 真
• 金额: $ 3.99万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Challenging Research (Exploratory)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-06-30 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K19813/
• 关键词: Σ2P完全問題; MaxSAT; robust solution; 組合せ最適化; 近似解法; ゲーム理論; マルチエージェントシステム

本研究ではΣ2P完全と呼ばれる，多項式階層において困難さのレベルがNP完全問題よりも一段階上のクラスの問題の解法の検討を行った．具体的には重み付き部分最大Satisfiability Problem (Weighted Partial MaxSAT) と呼ばれる典型的なNP完全問題（最適化問題としてはNP困難問題）を解く際に，敵対者が存在して解の一部を改竄する可能性を考慮し，改竄の影響を最小化する解を求める問題 (Robust Weighted Partial MaxSAT) がΣ2P完全となることを示し，この問題を解く厳密アルゴリズムを提案した．具体的には，近年発展が著しいSATソルバーと呼ばれる効率的な重み付き部分最大SAT問題を解くプログラムをサブルーチンとして用いて，最適解の上界値と下界値を段階的に狭めていくことで最適解を得るアルゴリズムを開発した．本解法の特徴は，防御側の視点での最適化問題と，攻撃側／敵対者側の視点での最適化問題を交互に解くことである．また，クリーク分割問題 (Clique Partition Problem, CPP) と呼ばれる汎用的な問題において，敵対者が存在するRobust CPPが，Robust Weighted Partial MaxSATとして定式化可能であることを示した．この結果は人工知能分野の難関国際会議であるPacific Rim International Conference on Artificial Intelligence (PRICAI-2022)でフルペーパーとして採録されている．また，Symposium on Multi Agent Systems for Harmonization 2022 Winter Symposium (SMASH22)で発表を行い，奨励賞を受賞している．

In this paper, we discuss the solution of NP complete problem in polynomial hierarchy. Maximum Satisfaction Problem of Specific Weight (Weighted Partial MaxSAT)?(Robust Weighted Partial MaxSAT)(Robust Weighted Partial MaxSAT) In particular, recent developments have led to the development of SAT solutions for the maximum SAT problem. The characteristic of this solution is that the optimization problem from the viewpoint of the defensive side and the optimization problem from the viewpoint of the attacking side/opposing side are mutually solved. Clique Partition Problem (CPP) is a robust partial problem that can be formulated into a general problem. Pacific Rim International Conference on Artificial Intelligence (PRICAI-2022) The Symposium on Multi Agent Systems for Harmonization 2022 Winter Symposium (SMASH22) was held in Beijing.

项目成果

Robust Weighted Partial Maximum Satisfiability Problem: Challenge to Σ2P-Complete Problem

鲁棒加权部分最大可满足性问题：对Σ2P完全问题的挑战

• DOI: 10.1007/978-3-031-20862-1_2
• 发表时间: 2022
• 期刊: Pacific Rim International Conference on Artificial Intelligence
• 作者: Sugahara Tomoya;Yamashita Kaito;Barrot Nathanael;Koshimura Miyuki;Yokoo Makoto
• 通讯作者: Yokoo Makoto