| 講演名 | 1994/4/27 否定数限定反転回路の複雑さについて 田中 圭介, 西野 哲朗, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 否定数限定回路とは,回路中で使用できるNOTゲートの個数をlog(n+1)に制限した組合せ回路である.本稿では,n変数を反転する否定数限定回路(反転回路)の複雑さについて考察する.本研究以前に知られている反転回路のサイズの最良の上界は,O(n^2(logn)^2)である.本稿ではまず,この上界をO(n(logn)^2)に改良できることを示す.次に,反転回路のサイズと深さに関してそれぞれ,5n+3log(n+1)-6および4log(n+1)+2の下界を示す.さらに,n変数を反転する否定数限定回路にある種の制約を加え,その回路サイズが超線形下界をもつような二つの特殊な場合を紹介する. |
| 抄録(英) | A negation-limited circuit is a combinational circuit which includes at most log(n+1)NOT gates.We call a negation-limited circuit which inverts n variables an inverter.In this paper,we investigate the complexity of the inverters.For the size of the inverters,we give a new O(n(logn)^2)upper bound as well as a 5n+ 3log(n+1)-6 lower bound.For the depth of the inverters,we give a 4log(n+1)+2 lower bound.Furthermore,we show two superlinear lower bounds on the size of inverters. |
| キーワード(和) | 回路計算量 / 否定演算子 / 反転回路 / 上界 / 下界 |
| キーワード(英) | circuit complexity / negation / inverter / upper bound / lower bound |
| 資料番号 | COMP94-6 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1994/4/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 否定数限定反転回路の複雑さについて |
| サブタイトル（和） | |
| タイトル（英） | On the Complexity of Negation-Limited Inverters |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 回路計算量 / circuit complexity |
| キーワード(2)（和/英） | 否定演算子 / negation |
| キーワード(3)（和/英） | 反転回路 / inverter |
| キーワード(4)（和/英） | 上界 / upper bound |
| キーワード(5)（和/英） | 下界 / lower bound |
| 第 1 著者 氏名（和/英） | 田中 圭介 / Keisuke Tanaka |
| 第 1 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science,Japan Advanced Institute of Science and Technology,Hokuriku |
| 第 2 著者 氏名（和/英） | 西野 哲朗 / Tetsuro Nishino |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science,Japan Advanced Institute of Science and Technology,Hokuriku |
| 発表年月日 | 1994/4/27 |
| 資料番号 | COMP94-6 |
| 巻番号（vol） | vol.94 |
| 号番号（no） | 26 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |