分岐プログラムに対する充足アルゴリズム構築による下界証明の研究

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

分岐プログラムの充足可能性問題とは，与えられた分岐プログラムが値１を出力するような変数入力（0/1割当）が存在するかどうかを判定する問題である．本研究では，未解決問題である計算量クラスNEXPとNC1の分離を導くため，幅限定分岐プログラムに焦点をあて自明な解法である全探索アルゴリズムよりも高速な充足可能性判定アルゴリズムの開発を目標としている．本年度は，k-Sub-SAT問題に対する非自明なアルゴリズムを設計することにより，幅２分岐プログラムのサイズが２乗に近い場合まで非自明な計算時間を達成する多項式領域決定性アルゴリズムの設計に成功した．これまで線形サイズの幅２分岐プログラムに対する充足可能性判定アルゴリズムが得られていたが，対応可能なサイズが更新されたことになる．k-Sub-SAT問題とは，入力としてk-CNF論理式（節の大きさが高々kであるCNF論理式）と２を法とする連立線形方程式が与えられ，その両方を満たす変数割り当てが存在するかを判定する問題である．この問題はk-SATを含む問題あり，kが3以上の場合はNP完全であることは明らかであるが，k=2においてもNP完全であることが知られている．既存研究では，k-Sub-SAT問題に対して全割当よりも高速な充足可能性判定アルゴリズムとして，指数領域決定性アルゴリズムや多項式領域乱択アルゴリズムが知られている．本研究では，k-Sub-SAT問題に対する多項式領域決定性アルゴリズムの開発に成功し，既存の多項式領域乱択アルゴリズムの計算時間とほぼ同等の性能を達成した．このアルゴリズムをサブルーチンとして用いることにより，幅２分岐プログラムの充足可能性問題に対する多項式領域決定性アルゴリズムを開発している．現在，本研究成果に関して論文投稿準備中である．