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

点击翻译按钮获取中文摘要

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