2026-05-12T13:20:05Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00234047 2025-01-19T09:53:44Z 1164:2592:11452:11598

内積と多数決関数に対する3段論理回路 Depth-Three Circuits for Inner Product and Majority Functions 天野, 一幸 Kazuyuki, Amano 3 段 OR ◦ AND ◦ OR 論理回路で，かつ入力側の各 OR 素子の入次数が高々 ???? であるものを Σ???? 3-回路と呼ぶ．本稿では，内積と多数決関数に対する Σ???? 3 型回路の構成について論じ，以下の 2 点を与える．(i) 2???? 変数内積関数 IP???? を計算する，素子数 2 0.952???? 以下の Σ2 3-回路，および，素子数 2 0.692???? 以下の Σ3 3-回路の明示的構成法，(ii) 多数決関数 MAJ???? を計算する Σ???? 3 型回路で，否定リテラルの利用が回路サイズの減少に寄与していると想定される構成法．両者とも，小さな入力サイズに対する最適な論理回路の計算機による探索とその一般化により得られたものである． A Σ???? 3-circuit is a depth-three OR ◦ AND ◦ OR circuit in which each bottom gate has fan-in at most ????. In this work, we investigate the Σ???? 3-complexity for the inner product function the majority function and give the following two results. (i) We give an explicit construction of a Σ2 3-circuit of size smaller than 2 0.952???? for IP???? as well as a Σ3 3-circuit of size smaller than 2 0.692????. (ii) We present a construction suggesting that the use of negations leads to a reduction in Σ???? 3-complexity for MAJ????. All these results rely on efficient circuits or formulas on a small number of variables that we found through a computer search. 情報処理学会 2024-05-01 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/234047 2188-8566 AN1009593X 研究報告アルゴリズム（AL） 2024-AL-198 8 1 1 https://ipsj.ixsq.nii.ac.jp/record/234047/files/IPSJ-AL24198008.pdf application/pdf 785.2 kB