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

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

• 批准号: 22K11909
• 负责人: 玉置 卓
• 金额: $ 2.66万
• 依托单位: University of Hyogo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2026-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K11909/
• 关键词: 厳密アルゴリズム; 近似アルゴリズム; 計算困難; 制約充足問題; 充足可能性問題; アルゴリズム; 計算限界; 量子計算

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

The first purpose of this study is to design and analyze the computational limit proof technique using the branch limit method. The mathematical planning method explored by the bureau is completely different, and the calculation limit proof technique is used effectively. The second purpose of this study is to conduct research on the current situation and the utilization of specific techniques. The constraint sufficiency problem and the research on the combination of quantum computing are carried out. 従来から行われているConstraint sufficiency problem に対するquantum アルゴリズムの Research を発开させるとともに, Quantum version of the constraint sufficiency problem is solved by the classical quantum system research group. This year's first goal is the following results. Fomin and Kratsch, Exact Exponential Algorithms, Exact Exponential Algorithmsではパーマネント, There is a direction of the road, ビンパッキング, a color number and a problem, 2^nのようなcalculate timeをhold つアルゴリズムが introduction されている. The principle of inclusion is that the partial set is closed and the point is calculated. #SAT is similar to the point. This study is, Including the principle of theoretical circuit の#SAT problem として formalization することで, 2^n time よりHigh speed なアルゴリズムを design できる occasion があることをshow した. The specific one, Formalization and use of theoretical circuits and AC^0[m] are part of the formula and include the principle of exclusion. Special mod 2のnumberえ上げについては様々なquestionがこのconditionを満たしている.

项目成果

Carnegie Mellon University(米国)

卡内基梅隆大学（美国）

Suguru TAMAKI's Website

玉木胜的网站