| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-04-17 13:30 しきい値論理回路のエネルギー複雑度と段数について ○内沢 啓・西関隆夫（東北大）  COMP2009-4 |
|
| 抄録 | （和） | ブール関数$f$がしきい値回路$C$で計算できるとし，$C$のエネルギー複雑度が$e$であるとする．したがって，どんな入力に対しても，回路$C$のしきい値素子の高々$e$個しか“1”を出力しない．このとき，関数$f$は段数$2e+1$のしきい値回路$C'$でも計算できることを示す．なお，$C$のサイズ（素子数）が$s$であるとき，$C'$のサイズは$2es+1$である． |
| （英） | Suppose that a Boolean function $f$ can be computed by a threshold circuit $C$ of energy complexity $e$. Thus, at most $e$ threshold gates in $C$ output ``1'' for any input to $C$. We then prove that the function $f$ can be computed also by a threshold circuit $C'$ of depth $2e+1$. If the size of $C$ is $s$, that is, there are $s$ threshold gates in $C$, then the size of $C'$ is $2es+1$. |
|
| キーワード | （和） | しきい値回路 / エネルギー複雑度 / サイズ / 段数 / 回路計算量 / ブール関数 / / |
| （英） | Threshold circuit / Energy complexity / Size / Depth / Circuit complexity / Boolean function / / | |
| 文献情報 | 信学技報, vol. 109, no. 9, COMP2009-4, pp. 21-28, 2009年4月. | |
| 資料番号 | COMP2009-4 | |
| 発行日 | 2009-04-10 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2009-4 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2009-04-17 - 2009-04-17 |
| 開催地（和） | 京都大学 |
| 開催地（英） | Kyoto Univ. |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2009-04-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | しきい値論理回路のエネルギー複雑度と段数について |
| サブタイトル（和） | |
| タイトル（英） | Energy Complexity and Depth of Threshold Circuits |
| サブタイトル（英） | |
| キーワード(1)（和/英） | しきい値回路 / Threshold circuit |
| キーワード(2)（和/英） | エネルギー複雑度 / Energy complexity |
| キーワード(3)（和/英） | サイズ / Size |
| キーワード(4)（和/英） | 段数 / Depth |
| キーワード(5)（和/英） | 回路計算量 / Circuit complexity |
| キーワード(6)（和/英） | ブール関数 / Boolean function |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 内沢 啓 / Kei Uchizawa / ウチザワ ケイ |
| 第1著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 西関 隆夫 / Takao Nishizeki / ニシゼキ タカオ |
| 第2著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-04-17 13:30:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2009-4 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.9 |
| ページ範囲 | pp.21-28 |
| ページ数 | 8 |
| 発行日 | 2009-04-10 (COMP) |
[研究会発表申込システムのトップページに戻る]