多項式階層を登る：Σ2P完全問題への挑戦
-
- 横尾 真
- 研究代表者
- 九州大学
研究課題情報
- 体系的番号
- JP22K19813
- 助成事業
- 科学研究費助成事業
- 資金配分機関情報
- 日本学術振興会(JSPS)
- 研究課題/領域番号
- 22K19813
- 研究種目
- 挑戦的研究(萌芽)
- 配分区分
-
- 基金
- 審査区分/研究分野
-
- 中区分61:人間情報学およびその関連分野
- 研究機関
-
- 九州大学
- 研究期間 (年度)
- 2022-06-30 〜 2024-03-31
- 研究課題ステータス
- 交付
- 配分額*注記
- 6,240,000 円 (直接経費: 4,800,000 円 間接経費: 1,440,000 円)
研究概要
人工知能の研究において，NP完全と呼ばれる，指数的な可能性の中から望ましい性質を満たす解を試行錯誤的に探索する問題が中心的な役割を果たしている．理論的には効率的な厳密解法は存在しないことが予想されているが，いくつかの問題 (充足可能性問題, 混合整数計画問題等) で大規模な応用事例に対応可能な効率的なプログラムが得られている．本研究では，Σ2P完全と呼ばれる問題の近似アルゴリズムを開発することを目標とする．直感的には，Σ2P完全問題を解くためには指数的な個数のNP完全問題を解くことが必要とされ，この問題はNP完全問題よりも格段に難しい問題となる．
詳細情報 詳細情報について
-
- CRID
- 1040292706147678208
-
- 本文言語コード
- ja
-
- データソース種別
-
- KAKEN