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

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

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

分支程序的充分问题是一个问题，它决定了给定的分支程序是否具有输出值1的变量输入（0/1％）。在这项研究中，为了指导计算类Nexp和NC1的分离，这是一个尚未解决的问题，目标是将重点放在宽度有限的分支程序和自我方面。今年，通过在K-SUB-SAT问题上设计非明显的算法，我们成功地设计了实现非自我的计算时间的多边区域决定性算法，直到两分支计划的大小接近两个。到目前为止，已经获得了一个有线性大小的2个分支程序程序的法官算法，但已更新了可使用的大小。 k-sub-sat问题给出了k-cnf逻辑公式（CNF逻辑公式，该公式在截面的大小上很高），并且可以确定是否存在的变量分配。这个问题的问题包含k-sat，很明显，如果k为3或更多，则NP是完美的，但众所周知，k = 2是完美的。现有的研究表明，指数区域决定因素算法和多态艺术主义是一种算法，该算法比K-SUB-SAT问题的总分配快。在这项研究中，我们成功地开发了有关K-SUB-SAT问题的多段介质算法，并达到了与现有多态性算法的计算时间几乎相同的性能。通过将此算法用作子例程，在满足两个分支程序的问题上开发了多边区域确定的算法。目前，我们正在准备有关这项研究结果的论文。

项目成果

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