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

约束满足问题的新系统研究

基本信息

批准号：
22K11909
负责人：
玉置卓
金额：
$ 2.66万
依托单位：
University of Hyogo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2026-03-31
项目状态：
未结题

项目摘要

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

这项研究的第一个目的是设计和分析受计算极限证明技术启发的算法，该算法的目的是进行组合研究。除了开展约束满足问题的量子算法的常规研究外，我们还将致力于约束满足问题的量子版本的经典算法和量子算法的研究。今年，我们在第一个目标中获得了以下成果。设计精确指数时间算法的强大技术是包含/排除原理，例如，教科书 [Fomin 和 Kratsch，精确指数算法] 使用永久、有向哈密顿路径、装箱、对于图色数等问题，引入了计算时间为 2^n 的算法。包含/排除原理与#SAT 类似，它计算所有子集的总和。在本研究中，我们通过公式化表明了这一点。将包含/排除原理作为逻辑电路的 #SAT 问题，可以设计比 2^n 时间更快的算法。具体来说，当使用包含和排除原理使得公式中使用的逻辑电路可以是AC^0[m]的子类时就是这种情况。特别是，关于mod 2枚举的各种问题满足这个条件。