2021年9月 - 2023年3月
強指数時間仮説に基づく計算限界の理解と探究
日本学術振興会 科学研究費助成事業 学術変革領域研究(A) 学術変革領域研究(A)
本研究の目標は強指数時間仮説の知見を深め、将来的に仮説の否定につなげるための研究を遂行することである。そのため、2021年度は既存研究の調査を行い、強指数時間仮説下における計算限界の結果をまとめることを目標とした。既存研究の調査は概ね終了したが、全体を手軽に参照できる形でまとめることはできていない。調査の過程で、強指数時間仮説よりも強い仮説(Super Strong Exponential Time Hypothesis:SSETH)について調査を進めることがあり、この仮説を否定することが直近の目標になることを確認した。
SSETH とは節内の変数の数が高々、k 個に制限された和積標準形論理式の充足可能性問題において、既存の最速アルゴリズムの計算時間より真に高速なアルゴリズムは存在しないという仮説である。これは強指数時間仮説よりもかなり強い仮説であり、これをまず否定するために新たなアルゴリズム設計を行うことが重要であると考え、SSETH に関する研究を実施したが、既存アルゴリズムの計算時間の改良には至らなかった。しかし、既存の最速アルゴリズムが苦手なインスタンス集合に対しては、別のアプローチで高速に解けることがわかった。
また、充足可能性判定アルゴリズムの設計技法の理解のために、幅2分岐プログラムの充足可能性判定アルゴリズムの設計を試みた。その結果、幅2分岐プログラムのノード数が入力変数の個数の線形個であれば、全探索よりも指数的に高速なアルゴリズムを設計することができた。さらなる高速化の手法への検討も既に行なっており、別の充足可能性判定問題を解く必要があることを確認している。
SSETH とは節内の変数の数が高々、k 個に制限された和積標準形論理式の充足可能性問題において、既存の最速アルゴリズムの計算時間より真に高速なアルゴリズムは存在しないという仮説である。これは強指数時間仮説よりもかなり強い仮説であり、これをまず否定するために新たなアルゴリズム設計を行うことが重要であると考え、SSETH に関する研究を実施したが、既存アルゴリズムの計算時間の改良には至らなかった。しかし、既存の最速アルゴリズムが苦手なインスタンス集合に対しては、別のアプローチで高速に解けることがわかった。
また、充足可能性判定アルゴリズムの設計技法の理解のために、幅2分岐プログラムの充足可能性判定アルゴリズムの設計を試みた。その結果、幅2分岐プログラムのノード数が入力変数の個数の線形個であれば、全探索よりも指数的に高速なアルゴリズムを設計することができた。さらなる高速化の手法への検討も既に行なっており、別の充足可能性判定問題を解く必要があることを確認している。
- ID情報
-
- 課題番号 : 21H05839
- 体系的課題番号 : JP21H05839