| 講演名 | 2008-10-10 ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ 内沢 啓, 瀧本 英二, 西関 隆夫, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ブール剰余関数MOD_m:{0,1}^n→{0;1}を計算するしきい値論理回路Cは,入力x∈{0,1}^nに含まれる1の個数がmの倍数であるときに"0"を出力し,それ以外のときに"1"を出力する.ここでnとmはn≧1,m≧2なる整数である.m=2のときMOD_mはいわゆるパリティ関数である.回路Cのサイズをsとする.即ちCはs個のしきい値素子から構成されているとする.またCのエネルギー複雑度をeとする.即ちCがMOD_mを計算するとき,高々e個のしきい値素子しか"1"を出力しないとする.このとき,MOD_mを計算する任意の回路Cにおいてn/(m-1)≦s^eであることを証明する,nとmは回路の設計に依存しない値であるので,(n-1)/mも依存しない.一方,sとeは回路Cの設計によって定まり,s^eはsとeの単調増加関数である.したがって,MOD_mを計算する回路Cのサイズsとエネルギー複雑度eの間には,トレードオフの関係がある. |
| 抄録(英) | A threshold logic circuit C computing a Boolean function MOD_m: {0,1}^n→{0,1} outputs "0" if the number of ones in the input x∈{0,1}^n to C is a multiple of m and, otherwise, C outputs "1", where n≧1 and m≧2. The function MOD_2 is the so-called parity function. Let s be the size of the circuit C, that is, C consists of s threshold gates, and let e be the energy complexity of C, that is, at most e gates in C output "1" for any input x∈{0,1}^n when C computes MOD_m. In the paper, we prove that n/(m-1)≦s^e for every circuit C computing MOD_m. Both n and m, and hence n/(m-1), do not depend on the design of C. On the other hand, s and e depend on the design of C, and s^e is monotonically increasing with respect to s and e. Therefore, the inequality n/(m-1)≦s^e implies that there is a tradeoff between size s and energy complexity e of a threshold circuit C computing MOD_m. |
| キーワード(和) | しきい値回路 / エネルギー複雑度 / サイズ / ブール剰余関数 / パリティ関数 / 回路計算量 / ブール関数 |
| キーワード(英) | Threshold circuit / Energy complexity / Size / MOD function / Parity function / Circuit complexity / Boolean function |
| 資料番号 | COMP2008-42 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2008/10/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ |
| サブタイトル（和） | |
| タイトル（英） | Size-Energy Tradeoff for Threshold Logic Circuits Computing MOD Functions |
| サブタイトル（和） | |
| キーワード(1)（和/英） | しきい値回路 / Threshold circuit |
| キーワード(2)（和/英） | エネルギー複雑度 / Energy complexity |
| キーワード(3)（和/英） | サイズ / Size |
| キーワード(4)（和/英） | ブール剰余関数 / MOD function |
| キーワード(5)（和/英） | パリティ関数 / Parity function |
| キーワード(6)（和/英） | 回路計算量 / Circuit complexity |
| キーワード(7)（和/英） | ブール関数 / Boolean function |
| 第 1 著者 氏名（和/英） | 内沢 啓 / Kei UCHIZAWA |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 2 著者 氏名（和/英） | 瀧本 英二 / Eiji TAKIMOTO |
| 第 2 著者 所属（和/英） | 九州大学大学院システム情報科学研究院情報理学部門 Department of Informatics, Faculty&Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 第 3 著者 氏名（和/英） | 西関 隆夫 / Takao NISHIZEKI |
| 第 3 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 発表年月日 | 2008-10-10 |
| 資料番号 | COMP2008-42 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 237 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |