対数領域計算モデルの計算限界の解明

本研究の最終目標は『L vs. P』問題を解決する事であり，そのための足掛かりとして現在の分岐プログラムの裁量下界を改良することを目標としている．計算量クラスLに入っていないであろうと信じられる木構造関数値評価問題を解く分岐プログラムを解析し，これまでそのサイズ下界がnの1.5乗であることは確認されていた．この下界がより大きく，超多項式サイズ必要であることを証明すれば本目標は達成される事となる．研究実施計画に基づき，まずはRead-Onceという制限を設けた分岐プログラムのサイズ下界を解析した．これにより，上界と一致する下界を示すことができ，その値はnのlogn乗と超多項式となる理想的なものであった．この結果はSTOCSという国際会議へと投稿され，採択率25%程の状況で採択されている．次の研究課題として，Read-Onceという制限を外した，一般的な分岐プログラムの下界解析へと取り組んだ．こちらは上界と一致する下界が2分木かつ高さ3の木構造を持つ問題までしか証明されていない状況であった．ここから発展させ高さ4の木構造を持つ問題の分岐プログラム下界を示すよう研究を進めていったが，思うような進展は得られなかった．Read-Onceという制限の下では上界と一致する下界が示せたということから，そこから得られる知見を用い，Read-Onceとは別の方向からの制限である深さに関係する制限を加える事で，既知の下界よりも3倍ほど大きい下界を示すことができた．しかしこの手法では既知の下界よりも大きなオーダーを示す下界を示す事は難しいと結論付けた．

本研究の最終目標は『L vs. P』問題を解決する事であり，そのための足掛かりとして現在の分岐プログラムの裁量下界を改良することを目標としている．計算量クラスLに入っていないであろうと信じられる木構造関数値評価問題を解く分岐プログラムを解析し，これまでそのサイズ下界がnの1.5乗であることは確認されていた．この下界がより大きく，超多項式サイズ必要であることを証明すれば本目標は達成される事となる．研究実施計画に基づき，まずはRead-Onceという制限を設けた分岐プログラムのサイズ下界を解析した．これにより，上界と一致する下界を示すことができ，その値はnのlogn乗と超多項式となる理想的なものであった．この結果はSTOCSという国際会議へと投稿され，採択率25%程の状況で採択されている．次の研究課題として，Read-Onceという制限を外した，一般的な分岐プログラムの下界解析へと取り組んだ．こちらは上界と一致する下界が2分木かつ高さ3の木構造を持つ問題までしか証明されていない状況であった．ここから発展させ高さ4の木構造を持つ問題の分岐プログラム下界を示すよう研究を進めていったが，思うような進展は得られなかった．Read-Onceという制限の下では上界と一致する下界が示せたということから，そこから得られる知見を用い，Read-Onceとは別の方向からの制限である深さに関係する制限を加える事で，既知の下界よりも3倍ほど大きい下界を示すことができた．しかしこの手法では既知の下界よりも大きなオーダーを示す下界を示す事は難しいと結論付けた．