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

构造分支程序满足算法的下界证明研究

• 批准号: 22K11910
• 负责人: 照山 順一
• 金额: $ 1.91万
• 依托单位: University of Hyogo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K11910/
• 关键词: 充足可能性問題; 分岐プログラム; k-CNF; k-Sub-SAT; 計算量理論; 厳密アルゴリズム

分岐プログラムの充足可能性問題とは，与えられた分岐プログラムが値１を出力するような変数入力（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問題に対する多項式領域決定性アルゴリズムの開発に成功し，既存の多項式領域乱択アルゴリズムの計算時間とほぼ同等の性能を達成した．このアルゴリズムをサブルーチンとして用いることにより，幅２分岐プログラムの充足可能性問題に対する多項式領域決定性アルゴリズムを開発している．現在，本研究成果に関して論文投稿準備中である．

The problem of sufficient probability of divergence is to determine the existence of a number of input forces (0/1 cut). In this study, the unsolved problem is to calculate the separation between NEXP and NC 1, and to determine the development of NEXP and NC 1. This year, the k-Sub-SAT problem is designed for non-self-evident design. The design is successful in polynomial domain deterministic design. K-Sub-SAT problem, input k-CNF logic formula, 2-way continuous linear equation, 2-way continuous linear equation, 3-way continuous linear equation, 2-way continuous linear equation, 2-way continuous This problem is k-SAT problem containing The existing research on k-Sub-SAT problem is based on the complete cut, the exponential domain deterministic, the polynomial domain stochastic, and the high speed sufficiency possibility decision. In this paper, we successfully develop the deterministic polynomial domain for k-Sub-SAT problem, and achieve the same performance in terms of computational time and complexity for the existing polynomial domain. The problem of sufficient probability for a two-dimensional bifurcation of a polynomial domain is deterministic and the problem of sufficient probability for a polynomial domain is open. Now, the results of this research are in preparation for submission.

项目成果

A Satisfiability Algorithm for Deterministic Width-2 Branching Programs

确定性宽度2分支程序的可满足性算法

• DOI: 10.1587/transfun.2021eap1120
• 发表时间: 2022
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: Tomu MAKITA;Atsuki NAGAO;Tatsuki OKADA;Kazuhisa SETO;Junichi TERUYAMA
• 通讯作者: Junichi TERUYAMA

A Moderately Exponential Time Satisfiability Algorithm for Linear-Sized Deterministic Width-2 Branching Programs

线性大小确定性 Width-2 分支程序的中等指数时间可满足性算法

• 发表时间: 2022
• 作者: Tomu Makita;Atsuki Nagao;Tatsuki Okada;Kazuhisa Seto;and Junichi Teruyama
• 通讯作者: and Junichi Teruyama