定数段数回路における計算限界導出技法の研究

恒级电路计算极限推导技术研究

• 批准号: 21K11743
• 负责人: 脊戸 和寿
• 金额: $ 2.58万
• 依托单位: Hokkaido University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K11743/
• 关键词: 定数段数回路; 多数決関数; 充足可能性問題; 二元体上の連立線形方程式; 下界証明; 回路計算量; SATアルゴリズム

本研究の目標は、MOD6素子（素子に入力される1の数が6の倍数のときに0を出力する素子）とAND素子、OR素子、NOT素子を用いた定数段数回路において多数決関数の非自明な下界を得ることである。これまで知られている下界証明手法の改良だけでは、この目標を達成することは難しいと考えているため、定数段数回路に対する新たな証明技法の発見・構築が1つの目標となる。2022年度は前年度に実施した調査研究をもとに、2つの目標を立てて研究を実施した。1つ目は、AND素子、OR素子、NOT素子のみを使用した段数における多数決関数を計算するために必要な素子数の上下界の一致を目標としたが、これまでの結果を改良することはできなかった。2つ目は、MOD2素子（素子に入力される1の数が偶数のときに0を出力する素子）を利用した多数決関数の計算方法を模索した。これについても、思うような結果は得られなかったが、既存手法の調査研究をもとに和積標準形論理式の各節を高々 k 個に制限した k-CNF と 長さに制限のない二元体上の連立線形方程式を混合させた充足可能性問題である k-SUB-SAT の決定性多項式領域アルゴリズムを構築することができた。このアルゴリズムは、k-CNF の充足可能性問題を解く有名なアルゴリズムの1つである PPZ アルゴリズムの決定性版を利用しており、PPZ アルゴリズムとほぼ同じ計算時間で動作する。乱択多項式領域アルゴリズムや決定性指数領域アルゴリズムで同様の結果は既に知られていたが、決定性かつ多項式領域のアルゴリズムはこれまで知られていなかった。

The purpose of this study is to determine the number of segments in the loop by using the AND, OR and NOT elements. The improvement of the lower bound proof method of this paper is to achieve the goal of the new proof method of the discovery and construction of the goal of the first step. In 2022, the research and development plan was implemented in the previous year, and the research and development plan was implemented in the second year. 1. The number of segments used by AND elements, OR elements and NOT elements is calculated. The upper and lower bounds of the necessary elements are consistent. The result is improved. 2, MOD2 elements (element input force is equal to 1, element input force is equal to 0, element input force The result of this study is that there are k constraints on each section of the sum product standard form logic formula, k constraints on the length of the constraint, k constraints on the continuous linear equation on the binary, k constraints on the sufficient possibility problem, k constraints on the deterministic polynomial domain, k constraints on the construction of the deterministic polynomial domain. To solve the sufficiency probability problem of k-CNF, PPZ is the decisive version of PPZ. To calculate the action time, PPZ is the decisive version of PPZ. The result of the same analysis is that the domain of random polynomials is not determined, and the domain of deterministic polynomials is not determined.

项目成果

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

多数決関数の計算複雑さと未解決問題について

关于多数投票函数的计算复杂性和未解决的问题

• 发表时间: 2022
• 作者: Kaito Suzuki;Diptarama Hendrian;Ryo Yoshinaka;Ayumi Shinohara;脊戸 和寿
• 通讯作者: 脊戸 和寿

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