木構造関数値評価問題の計算領域下界
Lower bounds of Tree Evaluation Problems

概要

計算量理論において、ある二つの計算量クラスが同地関係かどうかを問う『対決問題』は理論的にも工学的応用にも非常に興味深いものである。本研究では対決問題のさらなる進展を狙い『L vs. P』問題を扱う。クラスLとクラスPは真に異なると強く信じられており、その証明のためにクラスPに属する問題を解く分岐プログラムの状態数下界が超多項式であれば良い事が分かっている。本研究では、これを示すために木構造関数値評価問題というとても興味深い特徴を持つ問題を扱い、一般的な制限であるRead-Onceという制限を加えた分岐プログラムの状態数下界が超多項式になる事を示した。。

産業界への展開例・適用分野

計算量下界解析の多くはより効率の良いアルゴリズムの構築に貢献する事が多く、今回対象としている計算量クラスは工業的応用の多い多項式時間アルゴリズムで解ける問題の集合である。

研究者

氏名	専攻	研究室	役職/学年
長尾 篤樹	通信情報システム専攻	岩間研	博士2回生

---