対数領域計算モデルのメモリアクセス回数による能力の比較

点击翻译按钮获取中文摘要

本研究の目的は分岐プログラムの下界解析の手法を確立する事である．そのために幅制限分岐プログラムが表現する論理関数に対する解析を行った．計算量理論では計算モデルに対する充足性問題を解くアルゴリズムの上界解析の手法が同計算モデルのサイズ下界の手法に応用される例が多く研究されており，本研究でも同様に幅に制限をもつ分岐プログラムに対する充足性問題を解くアルゴリズムの研究を進めている．その結果，一般的な論理関数の充足性問題に解空間の制限を付随させたSub-SATと呼ばれる問題を効率的に解くアルゴリズムを構築した．本結果を用いることで幅制限を持つ分岐プログラムを対象にした充足性問題に対しても高速に解を求めることができるようになり，これを応用させることで幅制限を持つ分岐プログラムに対しての下界解析の手法を構築できないかと模索している．本研究の期間は三年であり，三年目を終えた時点で分岐プログラムを入力とする充足可能性問題に対して三つの国際論文誌を出版することができ，多くの知見をえることができた．しかしながら，これらの成果は本研究の主目的であるメモリアクセス回数とは異なる制限に対する結果である．分岐プログラムという対数領域計算モデルが本質的にどういった性質のものなのかを解明するという点では前進しているが，これらの知見を応用させることで下界解析の手法を新たに構築するという点では課題が残っている状況である．分岐プログラムの一回読み制限や幅制限ををさらに緩和したモデルに対する下界解析の研究成果は世界でもまだ存在していない．その最初の一歩を踏み出すために分岐プログラムの様々な特徴について研究を進めている．本研究実績はその結果であると言える．