内積と多数決関数に対する3段論理回路

• Item type: SIG Technical Reports(1)
• 公開日: 2024-05-01
• タイトル: 内積と多数決関数に対する3段論理回路
• タイトル / 言語: en
• タイトル: Depth-Three Circuits for Inner Product and Majority Functions
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学情報学部
• 著者所属(英): en
• 著者所属(英): Faculty of Informatics, Gunma University
• 著者名: 天野, 一幸
• 著者名(英): Kazuyuki, Amano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 3 段 OR ◦ AND ◦ OR 論理回路で，かつ入力側の各 OR 素子の入次数が高々 ???? であるものを Σ???? 3-回路と呼ぶ．本稿では，内積と多数決関数に対する Σ???? 3 型回路の構成について論じ，以下の 2 点を与える．(i) 2???? 変数内積関数 IP???? を計算する，素子数 2 0.952???? 以下の Σ2 3-回路，および，素子数 2 0.692???? 以下の Σ3 3-回路の明示的構成法，(ii) 多数決関数 MAJ???? を計算する Σ???? 3 型回路で，否定リテラルの利用が回路サイズの減少に寄与していると想定される構成法．両者とも，小さな入力サイズに対する最適な論理回路の計算機による探索とその一般化により得られたものである．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-198, 号 8, p. 1-1, 発行日 2024-05-01
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会