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

阐明对数域计算模型的计算极限

• 批准号: 14J04867
• 负责人: 長尾 篤樹
• 金额: $ 1.22万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2014
• 资助国家: 日本
• 起止时间: 2014-04-25 至 2016-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14J04867/
• 关键词: Lower bounds; Branching programs; Computational complexity; Read-once restriction

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

The ultimate goal of this study is to solve the problem of L vs. P and improve the lower bound of discretion. The calculation quantity L enters into the middle of the calculation quantity L. The lower bound of the polynomial is necessary to prove that the object is achieved. Research implementation plan basis, but not Read-Once, limit, set up, diverge, change, change. The upper bound is consistent with the lower bound. The lower bound is consistent with the lower bound. The results of this study were submitted to the STOCS International Conference, with an acquisition rate of 25%. Second research topic: Read-Once limit analysis. The upper bound and the lower bound are equal to 2 minutes and 3 minutes respectively. The lower bound of the constraint is consistent with the lower bound of the constraint. The lower bound of the constraint is consistent with the lower bound of the constraint. The upper bound of the constraint is consistent with the lower bound of the constraint. The upper bound of the constraint is consistent with the upper bound of the constraint. The upper bound of the constraint is consistent with the It is known that the lower bound is 3 times larger than the lower bound. The lower bound of the known method is shown in the lower bound of the known method.