| 講演名 | 1999/7/21 否定数限定論理回路におけるマージングの複雑さ 天野 一幸, 丸岡 章, 垂井 淳, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では, 否定数限定論理回路一使用できるNOTゲートの個数を制限した, 2人力ANDゲート, 2人力ORゲート, NOTゲートからなる組合せ論理回路一における論理関数の複雑さについて考える. (n,n)-マージング関数とは, あらかじめソートされた2つの長さnの0,1系列 x_1≦・・・≦x_n, y_1≦・・・≦y_nを入力とし, これを併合した長さ2nの列z_1≦・・・≦Z_<2π> を出力する関数である. 本稿では, 使用できるNOTゲートの個数をt=(log_2log_2n-a)個に制限したときの, (n,n)-マージング関数の複雑さがΘ(2^an)であることを示す. |
| 抄録(英) | A negation-limited circuit is a combinational circuit that consists of AND, OR gates and a limited number of NOT gates. In this paper, we investigate the complexity of negation-limited circuits. The (n,n) merging function is a function that merges two presorted binary sequences x_1≦・・・≦x_n and y_1≦・・・≦y_n into a sequence z_1 ≦・・・≦z_<2n>. We prove that the size complexity of the (n,n) merging function with t=(log_2log_2n-a) NOT gates is Θ(2^an). |
| キーワード(和) | 回路計算量 / 否定数限定論理回路 / マージング / 上界 / 下界 |
| キーワード(英) | circuit complexity / negation-limited circuit / merging / upper bound / lower bound |
| 資料番号 | COMP99-26 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1999/7/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 否定数限定論理回路におけるマージングの複雑さ |
| サブタイトル（和） | |
| タイトル（英） | On the Negation-Limited Circuit Complexity of Merging |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 回路計算量 / circuit complexity |
| キーワード(2)（和/英） | 否定数限定論理回路 / negation-limited circuit |
| キーワード(3)（和/英） | マージング / merging |
| キーワード(4)（和/英） | 上界 / upper bound |
| キーワード(5)（和/英） | 下界 / lower bound |
| 第 1 著者 氏名（和/英） | 天野 一幸 / Kazuyuki Amano |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 GSIS, Tohoku University |
| 第 2 著者 氏名（和/英） | 丸岡 章 / Akira Maruoka |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 GSIS, Tohoku University |
| 第 3 著者 氏名（和/英） | 垂井 淳 / jun Tarui |
| 第 3 著者 所属（和/英） | 電気通信大学電子情報学科 Department of Communications and Systems University of Electro-Communications |
| 発表年月日 | 1999/7/21 |
| 資料番号 | COMP99-26 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 194 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |