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
项目状态：
已结题

项目摘要

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

在这项研究中，检查了多个层次结构的难度（称为σ2pPerfect）的难度水平，以解决高于NP完整问题的类中的类问题。具体来说，当解决典型的NP完整问题（加权部分Maxsat）时，称为最大加权部分问题（加权部分MaxSat）时，有一个敌人，并且解决方案的一部分是假定的。 MaxSat）要求最大程度地减少篡改影响的解决方案表明σ2P已完成，提出了一种严格的算法来解决此问题。具体来说，使用一个解决最大加权SAT问题的程序是最佳的，该程序在近年来是一个明显的子例程，并逐渐缩小了最佳解决方案的上下值。解决方案。该解决方案的特征是从攻击者 /敌人的角度从防御副观点和优化问题交替解决优化问题。此外，在一个普遍的使用问题中，有敌人的强大CPP称为Creek Split问题（Clique Partition问题，CPP，CPP），可以作为强大的部分Maxsat配制。该结果已在人工智能领域的艰难国际会议上记录在Pacific RIM国际人工智能会议（Pricai-2022）上。此外，它已在关于统一的2022冬季研讨会（SMASH22）的多代理系统研讨会上宣布，并获得了鼓励奖。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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
影响因子：
0
作者：
Sugahara Tomoya;Yamashita Kaito;Barrot Nathanael;Koshimura Miyuki;Yokoo Makoto
通讯作者：
Yokoo Makoto