Challenge to Sigma-2P complete problems: moving up in the polynomial hierarchy
-
- 横尾 真
- Principal Investigator
- 九州大学
About this project
- Japan Grant Number
- JP22K19813
- Funding Program
- Grants-in-Aid for Scientific Research
- Funding organization
- Japan Society for the Promotion of Science
- Project/Area Number
- 22K19813
- Research Category
- Grant-in-Aid for Challenging Research (Exploratory)
- Allocation Type
-
- Multi-year Fund
- Review Section / Research Field
-
- Medium-sized Section 61:Human informatics and related fields
- Research Institution
-
- Kyushu University
- Project Period (FY)
- 2022-06-30 〜 2024-03-31
- Project Status
- Completed
- Budget Amount*help
- 6,240,000 Yen (Direct Cost: 4,800,000 Yen Indirect Cost: 1,440,000 Yen)
Research Abstract
人工知能の研究において，NP完全と呼ばれる，指数的な可能性の中から望ましい性質を満たす解を試行錯誤的に探索する問題が中心的な役割を果たしている．理論的には効率的な厳密解法は存在しないことが予想されているが，いくつかの問題 (充足可能性問題, 混合整数計画問題等) で大規模な応用事例に対応可能な効率的なプログラムが得られている．本研究では，Σ2P完全と呼ばれる問題の近似アルゴリズムを開発することを目標とする．直感的には，Σ2P完全問題を解くためには指数的な個数のNP完全問題を解くことが必要とされ，この問題はNP完全問題よりも格段に難しい問題となる．
Keywords
Details 詳細情報について
-
- CRID
- 1040292706147678208
-
- Text Lang
- ja
-
- Data Source
-
- KAKEN