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

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

基本信息

批准号：
21K11743
负责人：
脊戸和寿
金额：
$ 2.58万
依托单位：
Hokkaido University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究の目標は、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 アルゴリズムとほぼ同じ計算時間で動作する。乱択多項式領域アルゴリズムや決定性指数領域アルゴリズムで同様の結果は既に知られていたが、決定性かつ多項式領域のアルゴリズムはこれまで知られていなかった。

这项研究的目的是使用MOD6元素在恒定阶段号电路中获得多数函数的非明显下限（当对元素的1s输入的数量为6时，输出0的元素是6的倍数）和一个和元素，一个或元素，以及不元素。我们认为，很难通过简单地改善已知的向下验证技术来实现这一目标，因此，一个目标是发现和构建用于恒定舞台电路的新验证技术。 2022年，根据上一年进行的研究，进行了两个目标。首先是匹配仅使用元素，元素或元素而不是元素计算大多数投票函数所需元素数量的上限和下限，但是到目前为止，结果尚未得到改善。其次，我们寻求一种使用MOD2元素来计算多数投票函数的方法（当元素输入的数量为偶数时，输出0的元素是偶数数字）。尽管我们无法获得我们期望的结果，但我们能够为K-Sub-Sat构建确定性的多项式域算法，这是一个令人满意的问题，它是K-CNF的混合物，k-cnf的混合物将总和产品标准逻辑方程的每个子句限制为大多数k，并且在大多数k中限制了与无长度约束的二重线性线性方程。该算法利用了PPZ算法的确定性版本，PPZ算法是解决K-CNF令人满意问题的众所周知的算法之一，并且在与PPZ算法的计算时间大致相同的计算时间内运行。对于随机多项式域算法和确定性指数域算法，已经知道了类似的结果，但尚无确定性和多项式域算法。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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
影响因子：
0
作者：
Tomu MAKITA;Atsuki NAGAO;Tatsuki OKADA;Kazuhisa SETO;Junichi TERUYAMA
通讯作者：
Junichi TERUYAMA

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

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