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

本研究ではΣ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)で発表を行い，奨励賞を受賞している．

本研究ではΣ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)で発表を行い，奨励賞を受賞している．