制約充足問題の新しい系統的な研究

本研究の第一の目的は, 計算限界証明技法に触発されたアルゴリズムの設計と解析を行うことである. 従来の分枝限定法, 局所探索や数理計画法とは全く異なる, 計算限界証明技法を活用したアルゴリズムは大きな可能性を秘めている. 現状では特定の技法が活用されているのみであるので網羅的な研究を行う.本研究の第二の目的は, 制約充足問題と量子計算の組合せの研究を行うことである. 従来から行われている制約充足問題に対する量子アルゴリズムの研究を発展させるとともに, 量子版制約充足問題に対する古典および量子アルゴリズムの研究にも取り組む.本年度は第一の目的について以下の成果が得られた. 厳密指数時間アルゴリズムを設計する強力な技法のひとつに包除原理がある. 例えば, 教科書 [Fomin and Kratsch, Exact Exponential Algorithms] ではパーマネント, 有向ハミルトン路, ビンパッキング, グラフ彩色数などの問題に対して, 2^nのような計算時間を持つアルゴリズムが紹介されている. 包除原理はすべての部分集合に関する和を計算するという点で#SATと類似性がある. 本研究では, 包除原理を論理回路の#SAT問題として定式化することで, 2^n時間より高速なアルゴリズムを設計できる場合があることを示した. 具体的には, 定式化に用いる論理回路がAC^0[m]の部分クラスにできるような包除原理の使い方をする場合である. 特にmod 2の数え上げについては様々な問題がこの条件を満たしている.

本研究の第一の目的は, 計算限界証明技法に触発されたアルゴリズムの設計と解析を行うことである. 従来の分枝限定法, 局所探索や数理計画法とは全く異なる, 計算限界証明技法を活用したアルゴリズムは大きな可能性を秘めている. 現状では特定の技法が活用されているのみであるので網羅的な研究を行う.本研究の第二の目的は, 制約充足問題と量子計算の組合せの研究を行うことである. 従来から行われている制約充足問題に対する量子アルゴリズムの研究を発展させるとともに, 量子版制約充足問題に対する古典および量子アルゴリズムの研究にも取り組む.本年度は第一の目的について以下の成果が得られた. 厳密指数時間アルゴリズムを設計する強力な技法のひとつに包除原理がある. 例えば, 教科書 [Fomin and Kratsch, Exact Exponential Algorithms] ではパーマネント, 有向ハミルトン路, ビンパッキング, グラフ彩色数などの問題に対して, 2^nのような計算時間を持つアルゴリズムが紹介されている. 包除原理はすべての部分集合に関する和を計算するという点で#SATと類似性がある. 本研究では, 包除原理を論理回路の#SAT問題として定式化することで, 2^n時間より高速なアルゴリズムを設計できる場合があることを示した. 具体的には, 定式化に用いる論理回路がAC^0[m]の部分クラスにできるような包除原理の使い方をする場合である. 特にmod 2の数え上げについては様々な問題がこの条件を満たしている.