2014年4月 - 2017年3月
回路計算量の下界証明におけるアルゴリズム的手法の研究
日本学術振興会 科学研究費助成事業 若手研究(B) 若手研究(B)
- 課題番号
- 26730007
- 体系的課題番号
- JP26730007
- 担当区分
- 研究代表者
- 配分額
-
- (総額)
- 3,380,000円
- (直接経費)
- 2,600,000円
- (間接経費)
- 780,000円
- 資金種別
- 競争的資金
理論計算機科学分野における最大の未解決問題であるP vs. NP問題の解決に向け，充足可能性問題のアルゴリズム設計による回路計算量の下界証明の研究を行った．本研究では閾値素子を一定数含む定数段数論理回路の充足可能性問題に対して，全探索よりも真に高速なアルゴリズムを設計することに成功した．また付随する結果として，最大充足可能性問題の新たなアルゴリズムが得られた．
- リンク情報
- ID情報
-
- 課題番号 : 26730007
- 体系的課題番号 : JP26730007